check the oil, is it milky at all? Perhaps a blown headgasket if performance is hurt. or improperly installed new head gasket, did you use sealer?
Or perhaps a slow leak, try searching for a leak or using a dye solution and an UV light to help trace down the leak.
Has your water pump ever been serviced? - Poor circulation can cause this, along with a bad cap valve.
Also, for the time being i would hard wire the fan to +12v (i would definitely recommend you putting it back on the temperature switch so your motor can remain at proper operating temperatures once the problem is solved)