I actually was in a very similar situation, but a little different. I bought a coin through Heritage's Make-an-offer program and when it came, the original Heritage sticker was still on it, from their 2011 February Long Beach auction

. When I tried to take off the sticker, not only did it leave residue, it also took off many flakes of the PCGS hologram

. To get off the residue, I foolishly tried acetone first

. Made the plastic all wavy and stuff.
I tried contacting Heritage to help me get it reholdered, and their representative seemed helpful at first. They first suggested Goo Gone for the residue. When I sent them after pictures though, they said they can send it for reholdering for me, except that I would be billed the costs. Because it was a make-an-offer item, it is considered to be sold "as is," so they wouldn't cover the reholdering costs. I eventually sent it in myself through a dealer.
Because yours, Tbone, was directly from Heritage and it was their stickers, maybe they'll pay up for the reholdering or send them in for you (probably with their large dealer discount?).
Regarding removing adhesive, I've found (a little too late) that Goo Gone does the trick without damaging the holder. It might leave a little smell and greasy feeling but that can be easily removed with some soapy water.
Good luck to you, Tbone, in trying to get Heritage to pay up!