OP, something that I've done in the past is just over-tightening the belt and using the extra stress to get the bolts out. Another few helpful tips for water pumps (i've done three).
1. your life will be a lot easier if you take the idler pulley off before you try and actually remove the water pump
2. you'll have to re-use the pipe that comes out of the pump. when you are putting this back in the new pump, WRAP THE THREADS IN SILICONE PLUMBING TAPE!!! Trust me, it will leak if you don't.
3. put a conservative amount of permatex on the seal that comes with the pump, this will help you guarantee a decent seal.
like i said, i've done several of these, feel free to PM with any further questions.