Hot and Cold water seem to be mixing
From your comment "re-plumbed for code reasons" and the odd behavior you're experiencing, I suspect the hot water circulation system might have been patched/crossed into the cold water system and/or the pump is faulty.

For a hot water circulation to work, the hot water pipes must be in a closed system (other than the obvious exit points like a faucet, dish or clothes water connection). The pump will draw hot water from the tank and circulated it back into the tank, for as long as the pump is running. You'll always have hot water on demand.

The pump is usually a passive device, meaning if the pump is off, water can freely move in and out of the pump without obstruction. But if you're not getting hot water when the pump is off, the pump maybe faulty. 

And you want to check to see if any hot water pipes got crossed/connected into cold water pipes. I suspect they are.