I just used this service Saturday and yesterday, here in California. I was pleased by how well it worked:
On my Android, I browsed to coffee.foldapp.com and touched the "Load Bitcoin" button.
I chose $5, because my wife's grande half-shot, soy, peppermint, iced, decaf mocha, with personal cup costs about $4.65.
I then touched the "Pay using your bitcoin wallet." link, which brought up Mycellium, with a payment of 16.628 mBTC (about $4).
I sent the payment, and within seconds, as soon as my payment hit the network, the Fold page showed a bar code, which I scanned at the register. (Obviously, Fold doesn't wait for the payment to be confirmed in a block.)
After the barista acknowledged my payment, I touched the "Refund" button to collect the $0.35 change. I used Mycellium's "copy to clipboard" function to get my refund address to the Fold app. The refund was sent instantly.
Summary: Quick, simple, and painless way to get a 20% discount at Starbucks by using Bitcoin.
Starbucks is not accepting bitcoin directly, they are using a bitcoin-to-giftcard service called Fold. Not the best method I would have hoped, but the more merchant accepting bitcoin the better.
That is true, Starbucks may not even be aware of this program. Some may ask: "Then who's giving the 20% discount?" As near as I can figure out, people sell their unwanted gift cards at a discount. Googling, I found
http://www.cardpool.com/sell/offers, where I got an offer to buy my hypothetical $20 Starbucks gift card for $14. This is a 30% discount, which allows sellers like Fold to offer a lower 20% discount and still make money. Fold does not say where they get their gift cards. At some point, the gift cards are stored electronically, which is how these apps get them to the buyer.