Thank you very much everyone for your replies.
The paste seemed to have done the trick, my PC now runs at a cool 33°C in idle, and goes up to about 40°C while I'm gaming. ^^
Also thank you for reminding me that i had to properly remove the old paste, got some alcohol and it worked like a charm.
As for what brand my PSU is, I am from South Africa, and yes I realize it is mostly a UK site but I find it useful so I use it. :P
And I think the PSU is some imported "thing" the name not being worth the mention, its still running perfect now tho.
Once again thank you to everyone for there input, and have a great day.