It's a software bug in a lot of the Samsung Galaxys' (at least 3 and S).
It apparently results from being sent an SMS longer than 160 characters that the sending phone splits up in several parts and then for some reason the sending phone (bad signal etc.) has to send one of the parts twice. When the receiving Galaxy receives one part of the long message twice, it generates a "protocol error" and stops accepting any messages from that carrier, and until the software is updated the "potential" problem exists.
The problem should get fixed by putting the SIM card into another phone and then sending an SMS to yourself, this should also retrieve all of your missing SMS.
Try updating your software, this bug should have been cured in the latest update.
Swapping the sim card to get it going again is just a work-a-round, not a fix.
If all else fails, use Go SMS instead