Sorry about that... was making dinner while replying to the post hehe
No, I left the old paste on. I haven't been having any heat issues with the old stuff that was on. Should I be reapplying paste every time that I remove the heatsink?
It's never a bad idea to re-apply the paste, but it's not always necessary.
It sounds like either a component is grounding out on the case somewhere, maybe a misplaced mobo stand-off. Located under the mobo and threaded for the mobo screws.
Either that or your power supply or motherboard are bad.
I would remove all the parts from the case and then assemble them on your table, out of the case, just to see if something is grounding out.