yep. 1st 4s did the same thing, took it back to A&TT. They said it was a hardware problem and replaced the phone. we tried the texting and it worked until we backed it up from the 3gs
Have you tried making sure the 3GS has the latest iOS version and all app updates and then backing it up again to iTunes. Then take the 4S and restore it to the newer backup?
Maybe the 3GS backup you're using is corrupted somehow.