Years ago I had a parts house sell me the wrong water pump & when you got on the highway it would heat up at idle it would go to the normal temp. Finally took the pump off & found it was trying pushing the water the wrong way. So I have to believe Adam is correct on this problem. 

Did you replace lower rad hose? If not there is a possibility that if the hose does not have internal spring in it, it could be collapsing under running conditions...just a thought.