I just used SMSBackup 2 days ago - backing up to Gmail. Worked like a charm. You can only backup 200 messages at a time, but when you hit backup again, it just continues with the next 200 msgs.
If you also want a copy on your SD card you can use SpriteBackup. It can backup both text messages and multimedia messages.
I haven't tried to recover any of my backups yet though - but Sprite usually make pretty reliable software.
/Ons