Did you have an AT&T SIM before? If so, simply doing the initial setup without a SIM at the store and replacing the sim later at home would not have worked for you?
I did have an ATT SIM on a Blackberry Pearl.
UPDATE: Girlfriend went to ATT - spent 4 hours there and they could not resolve the issue. Got on the phone with Apple...Apple says the phone is defective -- and DEMANDED $400 (above and beyond what she paid for the 32GM 3GS!) as collateral for a new phone to be shipped to the ATT Store on Monday!!!
Again, this is my first experience with the Iphone and Apple...I'm impressed!