Besides what you did to try to cure it, what was there anything major done prior to the problem showing up?
When you changed it, were the fins on the water pump bent?
I see you're in central, Wisconsin.
Any chance it had weak coolant and got cold enough to freeze solid?
What you're describing sounds all the world like some freeze-ups I have seen, where the block is solid ice down lower and the coolant at the top and around the head overheats and causes boil over.
In the cases I have had, where the block ices up, you can run the vehicle for hours and hours outside in the cold and the symptoms never go away, put it in a warm shop, or have the temperature get above freezing, where the block thaws out and all is back to normal.
In the case of a feeze-up, it overheats because there is flow blockage and the volume of what is liquid is reduced, the heater quits because liquid has turned to steam.
In even a semi-solid freeze up, if you fire it up, it USUALLY kills the water pump vanes and in one interesting instance I had, it actually burned up a water pump v-belt.
Chances are, what is circulating is only there because the head is the warmest part and heats up first.
It's only a possibility, but one worth mentioning in this weather and it goes out the window if you keep it in a warm garage every night.
.
Mark.