Area 51 X58 - i7 CPU Fan speed issues

Hi Guys - Please be gentle...i'm a newb.

Okay so when I boot, I get a warning flash up saying: "CPU Fan Error - Press F1 to continue."  If I do that I can boot into windows just fine and everything runs as it should.  I booted into the BIOS and checked and the fan was showing up as red and running at around 570RPM.

I opened up the case and gave it a good clean out, blasting away as much dust and grime as I could.  Booted back into the BIOS and checked and nothing had changed.  All the fans are spinning but the CPU fan does look a little slow to the naked eye.

Current specs are:

Mainboard : Asus P6T DELUXE V2
Chipset : Intel X58
Processor : Intel Core i7 920 @ 2666MHz
Physical Memory : 6144MB (3 x 2048 DDR3-SDRAM )
Video Card : ATI Radeon HD 4870 X2
Hard Disk : Seagate ST3750630AS ATA Device (750GB)
Operating System : Windows 7 Ultimate Professional (64-bit)

CPU Temps running idle are:

CPUTIN : 37 °C
CPUFANIN0 : 570 rpm
Core 1 : 48 °C
Core 2 : 43 °C
Core 3 : 48 °C
Core 4 : 45 °C

This stretches into the low to mid 50's when under load and the CPU Fan RPMs go up to about 750RPM.  (Load being WoW, Photoshop, Firefox, Outlook, ESET and iTunes)

The machine is about 2 years old and it's generally on all day and shut down of an evening but I still don't know why the fan speed should suddenly drop below the motherboard threshold.

Do I need a new fan? Or should I just set the alarm to ignore and keep an eye on the RPM's and Temps manually?  I'm not afraid of installing a new heatsink/fan but i'd rather not if I don't have to. 

Any thoughts/advice/warnings/bueller would be very welcome!

Thanks guys  :)

Syren