Weird RPM and Temp gauge Problem

[Chris28]

So I just finished installing a welded diff (sucks btw) and the new RP Sport braces and I go to drive my car. After about 15 minutes of driving and realizing how much better the vlsd is, I look at my cluster. The temp gauge is basically all the way at hot. I shut the car off real quick and pull over. I turn the key to "on" to check the temp, and it's right in the middle where it should be. I start driving again and the temp begins to go up again. I pull over and turn the car off again, only turning it back on to see the needle in the normal position. I sit there for a while idling and the needle stays stationary, a little on the cold side of the middle, right where it usually is. I rev the engine slowly and sure enough, as the engine speed increases, the temp gauge goes up too. If I let off the throttle, the temp comes back down slowly until it is at the normal position.

As I'm typing this I realized it could be my water pump, higher engine speed means things get hotter, and it the pump isn't circulating water then it would have the symptoms I'm having. What I don't understand is why after turning it off and back on would the temp gauge be at normal right away? It's really weird.

Setup: Mishimoto rad with altima e-fans. Radiator level was checked literally right before I took it out for a spin and it was topped off. I've been driving for weeks with no problems with overheating, then this happens right after I put on a new part.