Spiffyfitz,
My friend recently had this problem with his Mac Pro, but this was one of the original 2006 models so I'm not sure how much different the 2008 model is. So keep that in mind, I'm speaking of the 2006 model. His is way out of warranty (no Applecare) so we got to play with it without worry of voiding an already nonexistent warranty. We did 2 things, one of which fixed it. I'm not sure which.
The heat sink that was reporting the problem is actually the one in the memory bay, not the one visible near the PCIe slots. This is also called the MCH, memory control hub, or North Bridge
http://en.wikipedia.org/wiki/Northbridge_(computing). On the 2006 Mac Pro, with the 8800 installed, the cable for the temperature sensor on the heat sink is RIGHT below the front of the 8800 card when installed in slot 1. You can unplug that cable and it should say MCH underneath it. I would try to unplug that plug (it's only 2 wires) and plug it back in and see maybe if its just a loose connection.
We also actually completely removed the heat sink (not an easy task, not going to get into how to do that as your machine is under warranty still) and reapplied some new heat sink compound (AS5, Arctic Silver 5). We then reassembled everything and his machine is now working just fine.
Underneath the heat sink is thermistor
http://en.wikipedia.org/wiki/Thermistor attached via some sort of an epoxy. We did not remove that from the heat sink at all, just removed all of the old heat sink compound and reapplied a nice thin coat of AS5.
So either the act of replacing the heat sink compound or just removing/reseating the cable to the thermistor fixed his problem.
My guess in his case is it was just a loose connection. The heat sink was almost cold to the touch with the fans running full blast but istat still reading 259 degrees. Impossible. My friend seems to believe it was more related to the heat sink compound. But the heat sink compound doesn't get near the thermistor. The thermistor us underneath the heatsink but not near the heat sink compound.
So anyway, just try removing that cable and plugging it back in (when the machine is off and unplugged from the power source, of course). If it happens to my friend again, we'll probably see if we can just order a new heat sink. My guess is the heat sink would come from Apple with a new thermistor already attached. Worst case, it's the motherboard connection to the thermistor that has the problem.
I hope this makes sense. Sorry I'm all over the place with this reply, but maybe it will give you some ideas.
And remember, everything mentioned above is referring to a 2006 Mac Pro. I have not seen a 2008 Mac Pro up close so I can't tell you if it's the same or not.