Yea you are probably correct. Tear it down clean out intels paste and put in new. Not many have the guts to do that on a new cpu though.
One core being hotter than the others has nothing to do with TIM (unless there is an air bubble or something) and probably more to do with some sort of unevenness in the heatspreader or cooler. Sometimes it's just down to the silicon/package; as Idontcare found out in all of his lapping exercises, sometimes you just get a spiky core and no amount of lapping can de-spike it.
What kind of fans do you recommend? I was thinking of getting another 120mm in the front for intake and another 140mm on the top for exhaust? Would that be a good setup?
Sleeve fans should only be mounted vertically. Rifle/hybrid/ball/fluid-dynamic bearing fans can be mounted at whatever angle you wish. So do not use sleeve bearing fans for the top exhaust.
What I would do is get something cheap, such as a four-pack of Rosewill 120mm sleeve-bearing fans:
http://www.newegg.com/Product/Produc...82E16835200061 (Assuming you have enough 3-pin sockets for them, else you may have to either buy adapters or buy different fans)
You can then use them for front, side, and rear panels and have a spare or two left over in all likelihood.
Then if you need 120mm fans than can be mounted on the top or bottom of your case, you can currently get this pretty good fluid dynamic bearing fan for cheap at amazon if you're willing to wait up to 2 months to get it (it's backordered at the $4.99 price):
http://www.amazon.com/Arctic-Cooling.../dp/B002KTVFTE
Chances are you will be fine even without the top/bottom fans, though. I would just go without any top/bottom for a while and see how your temps are. If they are okay, then don't bother getting top/bottom fans unless you foresee an increased need for cooling in the future.