Polishtom: Your startup temps don't matter at all, unless its high. It doesn't mean anything at all for any other values.
k.jacko: Its obviously not seated well, and you'd have to reseat it. Make sure all the pins/screws are on tight. Might also want to check if the fan works. I've recommended the Tuniq tower to many people I personally know, and all of them are reporting superb temps (which I expect), so you should be getting good temps as well. Thermalpaste may have something to do with this, but I sincerely doubt that it had anything to do with your current problems. Replace the paste in any case (as in, re-apply).