What relay did he change? Was it the OVP relay? OVP is near the battery and looks like :
http://www.***************/secure/PartImages/0005405245.jpg
I had to replace mine just last week on Arthur Dalton's advice. Now my car starts properly.
On your cooling issue, is there any chance there could be air in the system or maybe not enough coolant? Was the radiator new? Try another T-Stat, 1st one may be faulty...
-GH