If this is a normal heat sink/fan setup there should be 4 screw that mount the fan to the sink. If this is the case you had no need of removing the actual heat sink. You would just remove the fan and replace just the fan, not the entire cooler.
By 'TIM' I assume that you mean the actual thermal compound and, yes, it is sensitive. Even though the base of the heat sink is a ground surface that is VERY smooth there are always imperfections. The thermal compound is designed to fill in those imperfections to give as much thermal transfer as possible. If it is not applied properly there can be minute air pockets that disrupt the heat transfer. This is probably your issue.
To be honest (in my opinion) the application of thermal paste and heat sink is best done before the motherboard is mounted in the case. Once the motherboard is mounted there is just too much 'flex' in the board to make locking it down easy without messing up the layer of paste.
Some notes...
1) In my opinion the best paste is made by Artic Silver.
2) As to removing old thermal compound... Use either a liquid form of contact cleaner or isopropyl alcohol of at least 92%. Never use rubbing alcohol as it will leave a film.
3) As to applying thermal compound... You want as thin a layer as possible while still having total coverage. I use the side of a plastic credit card to do this.
4) I don't really like them but you also have the option to use what I call a 'wax pack'. This is a simple patch that you put between the CPU and the heat sink. The thermal compound is embedded in the wax. You turn on the system and the heat melts away the wax leaving just the thermal compound. I'm not really sure as to why I don't like these things as I haven't read anything negative in their usage.
In your current situation I would probably suggest this method.
5) You can purchase Artic Silver thermal compound or 'wax packs' from such on-line stores such as http/tigerdirect.com or
http://newegg.com . You should also be able to purchase from any decent local computer shop.
As to initial thing that you should have probably done in just replacing the heat sink fan without actually removing the heat sink I do this about twice a year to clean out dust. I just use canned air to blow out the dust in the fins of the heat sink. I remove the fan and blow out all the dust. It is amazing how much builds up. Electronics are a magnet for dust! LOL! If you adopt this practice do it out side as it can make a mess.