Are you sure the new pump is working properly? With the engine running is the top pipe into the radiator nice and hot? Sounds to me like the water is not circulating properly. Running just the fans without the engine running isn't going to achieve much as the water pump is not circulating the cool water through the engine.

I'd personally be looking at taking the pump out and seeing if it is ok.