Was TIM attached to the cooler or did you have to apply some yourself, if so, how much did you use?
No TIM will cause heat problems, too much TIM will also cause heat issues.
Did you follow the instructions or make certain that the same amount of pressure on all sides was used to install the cooler to the CPU?
Edit, clarification