Ok, so here's the deal. Turns out I just spoke to someone high at Apple. THis person took some time to explain to me that the reason these devices are having this problem with SMS is because Sprint decided to allow limited functionality of the device when used on GSM Networks while the device is still under contract.
He went on to explain that these devices are meant to be used on Sprint's CDMA network, not any other network. He said that provisioning files that are given to your phone at the moment of activation come straight from Sprint's billing system and that phones that were subsidized by Sprint will not fully work on different networks even if they are unlocked.
They fixed one of my phones that wasn't sending SMS properly by changing something on the phone's profile but they said they couldn't fix my wife's because I needed to provide proof of purchase showing I paid full price at an Authorized Apple Reseller. So go figure... this is intentionally done by our greedy Telcos... I don't know what to do now.
Hope this helps...