You may also try a soft-face hammer or "deadblow" hammer. (And before anyone asks, yes, I'm serious.)

I used one on my old PB160 when I first got it (after trying the flexing and prying tricks previously mentioned) and found, a tap at the appropriate angle, with "just" the right amount of force, will loosen a stuck battery.

Just be careful - blunt objects and computer equipment don't mix.