I have the exact same issue as you are and it appears to be localized to the ISP that both Starbucks and Barnes and Noble uses. I can resolve my oc3.me domain even at the Starbucks using Google Internet a few miles away but the majority of the other Starbucks cannot. Based on what I can tell it looks like they use AT&T enterprise Internet services.
Please see the DIG results below:
mi6:~ JabuXm3$ dig ns oc3.me
; <<>> DiG 9.8.5-P1 <<>> ns oc3.me
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 3960
;; flags: qr aa rd ra; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 0
;; QUESTION SECTION:
;oc3.me. IN NS
;; AUTHORITY SECTION:
me. 604800 IN SOA upgrade.me. root.nmd.sbx16904.sanantx.wayport.net. 1 604800 86400 2419200 604800
;; Query time: 9 msec
;; SERVER: 192.168.5.1#53(192.168.5.1)
;; WHEN: Thu Jan 16 10:22:19 CST 2014
;; MSG SIZE rcvd: 105
I made some changes to my oc3.me DNS around early December as well and originally wrote it off as possibly a propagation issue, but then after a month of waiting patiently and being able to access my domain everywhere else it seems to be ISP problem at these stores...
I wish there was a way to get in contact with the ISP directly to fix the issue but I'm afraid that this is what you get when getting "free" wifi. :(