you can get amazon code from coinstar for 0% fee, then go to coinclub.io and convert to BTC.. i haven't used coinclub but they seem to have a good track record.
http://www.reddit.com/user/CoinClub_ioIt's an extra step from what you are describing, but simplest way i see to convert change to bits.
This is what I was thinking, so I mean it's possible already and that way you aren't getting hit twice (once by coinstar) but only a bit by coinclub.io