Using the integrated video Intel 945GM Express (Mobile) gave me this problem, but not with the external Nvidia accelerator (yeah I have a good laptop).
Even Simon Tatham knows about this 'bug'
At first I thought that the 945GM did not support a hardware cursor, but that is actually not the case.
Well, this turns out that it is not a bug related to PuTTY. It is a bug in the video driver. The most likely explanation was this:
I've seen this same problem personally on a GeForce2MX, and I investigated it carefully. I believe it is a bug in the GeForce2MX video driver. The I-beam cursor is supposed to invert whatever colour is underneath it, but it mistakenly inverts black to black. (My suspicion is that each RGB value x is mapped to 256-x instead of 255-x, or some equally easy typo.)
So off I went to Intel's website, downloaded the latest drivers, installed, rebooted, and viola! problem solved.
I hope this would help people facing the same problem, especially since the Mobile 945GM Express is so prevalent, I'm sure it affects a lot of people.