I had an over heat problem for a long time... I changed everything i thought of and still ... it over heated... was loosing coolant throught the overflow tank cause was getting way too hot... I was about to take it to the dealer when i realized that there was 2 temp sensors... one tells the electric fan to kick on and the other one controlls the gage. is it possible that you changed the wrong sensor? other than that and the electric fan and the TStat... there is nothing else in the system that could do that... but don't know where you are leaking coolant... if you know that... then it might just be a leak which can be fixed. when the car gets too low on coolant it will over heat real quick... they make die kits where you dump die in the radiator then check it with a black light to see where the coolant is leaking from.. pretty cheap

They are all right about the TStat... you should not run without one... especially in warmer weather cause it just gets too hot.