AT&T stores are sold out nationwide and have a 5 - 10 day lead time on getting more. The Apple Store in Seattle at University Village had about 200 people in the non-reserved line and about 40 people in line for those who reserved them. I waited about 30 minutes, went in, was out in 15 minutes or so with my 32GB iPhone

According to the peeps at the store, the line had originally stretched around the parking lot, opened at 730am, and were telling people who were arriving at the end of the non-reserved line to be patient, that they had plenty of phones in stock but might have a hour and a half to two hour wait to get inside.
As for the sim card in the new iPhones, they were the same as which came in the 3G iPhone. Because of the volume of sales nationwide, Apple was informing people that AT&T servers were overloaded and it could take up to 3 hours for the new phones to be activated. During the time between being bought and activated, you could only use the phone as a device on a wifi network until the servers registered the sim card and finished the activation process.