Hmm. I first I started thinking along the lines of "Wal-Coins", then maybe coins advertising local mom-and-pop shops.
But then I remembered Wal-Mart cards already exist.
I think the idea of other companies getting into bitcoins is good and will happen, but I think those into it for the advertising will want the cheapest possible medium, and probably one more familiar to the populace. I suspect plastic cards and possibly paper coupons/vouchers will be the preferred method--but the idea itself is still sound.
Too bad BitBills bit the dust, but isn't BitCardz coming about? Perhaps they could be contacted about this.