If your talking about the fan thats bolted to the engine then your going to need a new fan clutch. Quite expensive, around 250$ from a dealer.
If theres no heat through your vents its possible that you heater valve has gone bad or when the t-stat was replaced the garage didnt properly bleed the system and now theres a very low amount of coolant.
If you open the hood, with the engine cold, theres a black plastic cap on the plastic shrowd that surrounds teh fan that doesnt work. Open that up and if you dont see any coolant take it back to the garage and get them to bleed and top off the coolant system.