I had one go bad and it was exactly as you describe... hard start and crappy idle. The fan being on shows that the ECU thinks the engine is really hot. Do you have datascan? If you do, open it up and check the temp. I don't know how many ohms the sensor should have. I'm so sure that I would go ahead and buy a new sensor.
What Kory said is true, but I lean towards the coolant temp sensor. The most common ECU cause of a constantly running fan is a chip installed backwards. That isn't possible since it was fine before.