The only issue is you can only change cash into BTC, not coins.
This is from their website :
https://www.coinstar.com/bitcoin"Only cash is accepted. Coins cannot be used for Bitcoin transactions."
So you'd have to change your coins into bills and then use those to buy BTC... which means more fees.
Aww damn, when I initially heard about the news, I thought that they had added machines to convert actual coins into Bitcoin, just like their regular coin converters.
Still great, just because they have so many locations in the US.
It does seem like they've somewhat missed a great opportunity though.