Are you checking at "authorized retailers"? or official AT&T stores? Most AT&T stores are of the "authorized retailer" variety, at least in my area. On Cleveland's west side, there are maybe 5 or 6 AT&T stores, but only 1 of those is an official store. None of the retailers were carrying the Focus S on launch day, but the official store was. It's a bit confusing because even the authorized retailers usually have the full AT&T branding and look.
Try checking the store locator on AT&T's site and look for locations *not* labeled as authorized retailers. That's your best bet I think.
I bought mine late in the evening on launch day and the representative at the store told me it was the first one they'd sold, so I have my doubts about it selling out (unless Samsung didn't ship many to begin with, as someone else suggested)