Did you boot from the recovery partition and do a repair disk?
Starting in 2009 Apple put the temperature sensors for your Hardisk inside the disk and used special firmware on the disks. Some of the 2009 iMacs still have simple hardisks some have the new ones.
So you have to check this first.
If you replace the disk with one which does not have the sensor inside your fans will all spin up to maximum. You can overcome it by :
- use a compatible hardisk
- get an external temp sensor from OWC and plug it in the motherboard
- use software to override the Fan speeds
regarding compatible replacement disk: go to System Information and find out what disk you have (Manufacturer is important)
Get same manufacturer data disk - size and speed can be different.
You can also get a SSD and dramatically improve you iMac's speed!
Here is a video for HD replacement on a 7,1 iMac - note: this one has an external temperature glued to the HD
https://www.youtube.com/watch?v=2YsCTNVEYt8