NP, I was very frustrated because of the same situation and magically, after I resorted my iPhone 4S from my last backup and then removed the SIM Card the problem was solved : )I appreciate the input but this problem is happening on my other line which has a 4s on ios6 also.
I downloaded ibackupbot. When I tried to edit that file, the software said I have to purchase a full version of ibackupbot, which costs $35. Help me out here...100% fix:
it takes a little iPhone know how, but works 100%. When the phone comes from one carrier to another the c0m Apple mms_override.plist file isn't changed when restored from backup, even if you reset the network settings, so what you need to do is edit this file.
in iTunes make a backup of your phone
Download ibackupbot to edit your back up
find the file com Apple mms_override.plist
edit this file to look like this:
(it won't let me put in the first two lines of code because there is a web link in them, so leave the first two lines that are in the file)
click the little disk icon to save your changes, and then quit ibackupbot
open iTunes, and restore from your backup
TA FREAKIN DA!