Remember, you need to remove the remnants of the old thermal compound and add fresh goop when you reinstall a hsf.
Within the last year or two, Intel redesigned their OEM fans to emphasize quietness over cooling. There are a couple of things to try:
1) Your MB BIOS may allow you to specify the temperature set points at which the CPU fan starts to speed up and goes to max speed. On my MB, I set the CPU fan to start speeding up from 35C and reach max speed at 50C.
2) It may help to plug the CPU fan into a standard 3-pin fan header instead of the 4-pin CPU fan header. Under these conditions, the fan will rely on its built-in temp sensor to control its speed.