The paste helps fill in the microscopic gaps between the surface of the processor and the bottom of the heatsink. It looks smooth to the naked eye, but the paste, by filling in gaps, actually keeps air from being trapped between the two. The air heats up, and makes matters even worse.
There are enthusiasts who will actually use fine-grained sandpaper to smooth the top of the processor. It's a process (no pun intended) called "lapping" and is used by overclockers and folks who are trying to get maximum performances from their systems.
It's something of a dice roll, at this point. You may find that once the paste is reapplied, the system will come on line just fine. You may find, though, that it still won't turn on.
We'll have to take it a step at a time. (You're probably thinking, Who's 'we'?)
Keep us posted.
(Patio's really good at this. I do his "light work."
)