Here are some possibilities:
1) Did you install the new CPU cooler with the motherboard outside the case? If not, it's often just about impossible to completely install the 4-pin cooler retention system. Check out this post for info: http://www.tomshardware.com/forum/194385-31-part-assembly#t1184072
2) Is the cooler designed for a Pentium 4? Intel makes many different CPU coolers, some of which only work for lower-power CPUs.
3) Is there enough ventilation in the case? If cool air from the outside is not getting in, the CPU cooler won't be able to fully cool the CPU.
4) What cooler was on there before? Have you replaced the CPU or otherwise changed the internal configuration of the system?