Rule #1: Always use thermal paste
Rule #2: Not too much though!
Oh dear, sorry to hear you fried your chip. See rule #1. My guess is that your motherboard is still fine. Get a new chip, and you should be rockin' again.
This time, apply a paper thin layer of thermal paste (see rule #2) between the CPU and the heatsink. You can still use the shim if you want to, but then make sure to put grease in between all the 'layers' (Like this: Cpu, grease, shim, grease, heat sink, fan).
The grease will fill the small spaces between the CPU and shim and/or heat sink to avoid small air pockets that can turn VERY HOT, but also to increase thermal conductivity.
Good luck with it!