I went in to buy my 3G S on Friday, but of course they were sold out (I got there around noon-1:00). So I just ordered one right there in the AT&T store.
The salesperson told me that it should be here in about 7-14 days. I thought that sounded like a long time. He told me that in his experience for both the 2G iPhone and the iPhone 3G, the new shipment only took about 3-5 days.
However, I'm still waiting on mine too... Hope this helps.