I had the same problem. Pre-ordered two 16gb 4s' one Siri worked fine, other didn't. Decided the same day (14th) that I wanted two 32gb's instead so luckily there was still stock at AT&T so I swapped 16's for 32's. Wife's Siri worked perfect mine didn't. It didn't matter where we were, mine would not work but hers would no problem. I was also having a hard time just connecting to 3G as well when hers, again, would be fine. Called AppleCare, they swapped it out for another 32gb at the apple store. First swap didn't turn on right out of the box (like wouldn't power on at all), so they had to get yet another from the back. Second swap worked perfectly with no issues with Siri or 3G. All they could tell me was that there was some sort of receiver issue with the phone. My 4s has worked perfectly ever since.
My first 32gb was sluggish all around. With the swap, I can definitely tell the difference with speed everywhere, opening apps, the camera, Siri pops right to life now, etc. my wife also had to swap her 32gb out as well due to voice call connectivity issues (heavy echoing, terrible static, and cutting out). My call quality would be crystal clear, and hers, right next to me would be horrible. We tried everything to solve the Siri problems, as well as the connectivity problems before calling apple (soft reset, hard reset, wipe, restore, etc.), calling apple was the last option. After our swap everything seems to be fine with both 32gb'ers now...but!!! My wife's phone has gone back to the horrible call quality, while mine is still fine.
It seems that the Siri issue is not only one of bogged down servers, but also a hardware problem as well. So far I've had 3 brand new 4s' and my wife will be going on her third this week. I'm not telling everyone to rush to their apple stores to get their phones swapped, but if you notice an overall connectivity problem, or generally overall slower processing speeds I'd give apple a call.