On the east coast at least there is a CoinStar in most grocery stores and Wal-Mart's already.  This for me is a central point of the play - no one really needs any major capital expense to start this up.  The network of machines exists - and I'm 99% sure they are internet connected.  I'm not sure if distributing private keys at the location is feasible or if some sort of redemption code would make it simpler.

But this would reduce one of the major barriers to entry for people wanting to 'dip their toe' into btc.  Anyway - glad to see people are liking the idea - I hope it happens