If there is not paste/compounde/thermal pad on the fan that you took off, then there's a good chance the wrong fan was removed. You need to remove the "heatsink" as well which should be all one unit with the fan most likely clipped around it by a plastic square bracket. The heatsink has vented "fins" like a radiator to dissipate the heat. There should be a copper piece that makes contact with the processor itself. Between the copper piece and the processor is where there SHOULD be thermal compound, which can cool the processors down by 20 degrees Celsius or more!
Anyway, here is a link to what the heatsink and fan generally looks like: http://www.newegg.com/Product/Produc...82E16835200029