Another plus for antiseize. When trying to remove stuck plugs what you want to do is loosen it a bit, then go back the other way, then loosen some more. Just keep working it back and forth until it comes out, if you try to force it you're liable to tear up the threads in the head, especially if dealing with aluminum heads.

Also when tightening new plugs always hold the wrench close to the socket (assuming you're using a socket wrench) that way you don't A) tighten the plugs too much and B) end up cross threading the plugs or something similar.

 

I asked the shop if they used antisieze when they installed the new plugs, they confirmed that they had, just in case I removed the plugs and put some around the threads anyway.