Well, it turns out the fan wasn't fully dead. (It was turning slowly and making horrible grinding sounds). It appears that Vista SP2 upgrade (from sp1) required me to reflash my BIOS. I did as the nice lady in HP chat told me to do, and it seemed to make the fan work better (spins a bit faster and no grinding noise).
I have a few weeks before warranty runs out, and I am still perplexed at speedfan saying the temp is at 65C at idle and 85C at full load. But it has always been this way with speedfan, so I am hoping it is just speedfan misreading the values. Anyone have any insight on this? Is there another heat monitor out there that is more accurate?