AFAIK, McDonald's and Walmart take Discover; McDonald's alone has more locations than Starbucks.
That said, I can't remember the last time I've seen anyone use Discover anywhere. Starbucks has far better visibility; they still likely have the marketing advantage.
I've used Discover for years and can't really think of a place that didn't take it. I just recently canceled it and have switched to AMEX which I have already found a half a dozen places that don't take it.
IIRC Costco takes Amex (and not Discover) and Sam's Club takes Discover (and not Amex). It's been a while since I have darkened the door of a Sam's Club, but at the time I thought that was a pretty big win for Costco...
