By all means do what you feel you need to, but I'd recommend you hold off on doing anything major. If you've gone through and verified and reverified your settings (including My Info), and done the turn Siri on/off, reset network settings, etc....etc...etc... then great.
Let me tell you my story and it might help you....
My wife and daughter got brand new 4s's bought this past Saturday. Both worked flawlessly leaving the Apple Store. Got home and synced them up, and My wife's still worked flawlessly. My daughter's would not work at all, which is not good when it's a 14yr old and they have the patience of a hummingbird. I'm a 20+yr Apple veteran and ex-programmer, so I figured I could dig in and figure out what I needed to do to fix this. Spent entire weekend trying everything under the sun, nothing. Applecare discusson on Monday...zero help, waste of 20 minutes on hold. Finally, I made an appt to replace phone at the Apple Store and consult a genius (with all my notes) on wednesday. Had to be the phone I resolved. Picked my daughter up and low and behold and part the heavens, it was working and has worked fine all night and this morning. I'll get an update today when I pick her up from school, but I think there is some kind of network interaction that has different integration elements depending on individuals phones, contacts, apps, music, etc...that it takes time to develop an interaction or profile with the users phone. I don't know this for sure, but it clearly wasn't the hardware, or the availability of the internet connection, and why would one work in the same household and the other not. So naturally I'm speculating, but what else can you do when you can't get Apple to tell us anything or at least calm our fears. If Apple would say..."Hey be patient when you first sign up, as it takes awhile to build a profile and get it in the servers and populated, etc.,etc..", then we'd all have said "Yes Sir, thank you Sir", but that did not happen.
Long story short, I know it's frustrating, but reverify your settings and give it a couple of days. I spoke to some of my other colleagues about my experience and about half of them have a similar experience.
In the meantime, hopefully Apple will remember that we love their products and simply talk to us. Silence is worse than anything.
Hope this helps.
GatorMan........