A)
The chip isn't getting cooled. You can actually check without opening the case. Obviously, there's a sensor on it, otherwise Windows wouldn't be shutting down.
You can get Everest Home Edition, the current one, and it will tell you all the temperatures.
Your video card should be about ~40-55?, 80? for example, means the fans isn't running (or something else is wrong)
If you have a computer with a warranty, I have a sneaking suspicion that the video card is built on. Which leads to situation B
B)
The Video card is dying, you have to put a new one in.
And also, just to let you know, the warranties on pre-built machines is garbage. If you do send it in, You may or may not still have the data that's on the machine currently. Also, I couldn't imagine not being allowed to open my computer to fix something. Nothing takes that long to fix, so the very idea of sending it somewhere is a very distasteful idea to me.
Anyway, there could be a video card without a fan ... like ... this 5200:
http://www.superwarehouse.com/images/products/hp_QuadroFX-5200.jpg
Actually, it looks like that's the card that comes with some HP computers. In which case, obviously, it wouldn't be heat, since there never was a fan to cool it, just a heat sync. Which is a clear clue that it's dying, so that's a valid option as you surmised.
Not sure what else could cause video screwing up like that. Besides just bad video settings ... But, it was working before, so I think it's safe to say that isn't it.
Blame it on Microsoft, God does.