Just an update. I called the AT&T number 1.800.331.0500 and went through the command prompts to activate the phone. It took less than five minutes and I didn't have to speak to anyone.
I just wanted to confirm that this was the fix for me as well.
iTunes and my 4S were not interested in displaying any kind of activation options for me. I finally gave up and called CS, right after entering my phone number it said I had a phone that needed to be activated. I followed the prompts and was up and running immediately, no activating on the phone or in iTunes required!