the Intel heat sinks are a pain sometimes to seat properly. you may think all 4 pins are pushed through right but aren't. best way to do it is with the mother board out of the case. Anyways, try re-seating the pins in a criss-cross pattern.
Swifty's got the right idea. The thermal compound itself will have a negligible effect the temps but almost always when they go up after removing the cooler its because it wasn't seated properly back down.
Push hard. You should feel a slight snap or click.