Figured it out, I hope. I opened it up once more and apparantly the paste didn't make contact with the heatsink. I have an 80 gig whle my friends ps3 was a 40 gig so they look totally different inside.
Anyway, I first did the "even spread" over both chips but like I said, no contact with the heatsink.
I then cleaned it all off and applied 2 small chunks in the center of the chips and pressed down a bit so it would make contact and spread with help of the heatsink and now it works again! The fan is still medium though so maybe I should've applied even more paste to make it run more smooth.
Checked out this tutorial regarding the arctic paste
PS3 Arctic Silver Proper Application on Heat Sink - YLOD Prevention - YouTube
At least it's working again, even if I had hopes the fan would run more quiet.