You normally get this when you have no coverage ... it will offer a resend in the multithreaded SMS window.
If not ... I suggest you may have forgotten to run the carrier wizard and soft reset afterwards. This will setup the device for the new carrier stuff. It should off the wizard automatically when a new SIM is detected.
UK HTC HD2 - 16GBuSDHC, Energy 21683 Oct 25 2010, Latest Evo 2.2 Android 25 Oct, 2.12.50.02_2 radio, PI2009, eWallet, Pnotes5.4, CO'08, CPL8, 1calc3, TM/PM/PR08, 40iPlay, myPlayer/Coreplayer, Tube2, SkyMobile, GMaps, SKtools,HTC Sprite,Resco Media Suite,gyrator2,Zooomer.
Samsung Galaxy Tab ..