Okay...tried activation with the new SIM card per AT&T recommendation, no dice. Utterly pissed, I went to return the iPhone for a refund, so I went back to the Apple Store at Sagemore in Marlton, NJ. However, when I went in, I decided to give it one last try with the Genius Bar. I explained the issue, and the genius waited on the phone for about 45 minutes. After doing everything over the phone, he said the phone should be activated within an hour and a half. The genius was quick to blame the process on AT&T.
I went to dinner, and came in about 2 hours later, and saw an email saying that AT&T was transferring the number, and that I should be able to make outbound calls and use the phone. However, when I sync with iTunes, I still receive the "Your activation requires additional time to repeat." I called one of the numbers provided on the forum (thanks guys!) and got a live rep. He confirmed that the SIM card was indeed activated. In fact, he said I could take the SIM out and put it in any other phone and I would be able to place calls. However, he said that the iTunes activation is severely backed up and it is unable to unlock the phone. Unlike the Apple genius, he was very conscientious of his words. He said that its not an Apple problem, or an AT&T problem, and that they share responsibility as it is a joint venture. He sounded much more professional than the genius and was much more helpful as well.
So, as a lot of folks on the forum initially said, this is Apple's problem, not AT&T. Right now, I'm on hold in the queue to try and unlock my iPhone manually. We'll see what happens.
**** Apple. If this doesn't work after this, I'm taking it back. And you better believe I'm not paying some god damn restocking fee.