Just traveled overseas and used a different sim card with my phone. Not only does this screw up iMessage while overseas (it shouldn't), but for 2 weeks after getting back iMessage would occasionally just not receive texts. Did 3 Network resets and the last one (at 2 week mark) finally fixed it.
I'm sure this is more verizon's fault, but Apple needs to work around it.