Update: Lenovo T42 "Fan Error" on boot

First of all my notebook is T61, not T42. Sorry if this confused anyone.

I was able to remove heat sink with the fan - thanks for encouragement, I was not sure if I could the job. Here are the photos I took http://imgur.com/a/AHMV2. Fan itself looks clean and I don't see any dirt or debris in it. So, should I just clean thermal paste off the components, reapply the new one and give it a go before installing new heat sink? Thanks again for your help!