The same exact problem happened to me twice. The first time was over a week ago. Messages app kept quitting, and shortly after I restarted my iPhone, all of my contacts were lost. It's probably unrelated, but I did inadvertently open the Verizon Backup Assistant app the day before this happened. I immediately closed the app without doing anything to my contacts. I was also using iOS 5.1.1, since it had been working well and I saw no need to upgrade (especially because of google maps, etc). I restored my iPhone using a backup I had fortunately made a few weeks prior, and got back all contacts except for recently added ones.
Just a few days ago, the same thing happened again, this time overnight after restarting my phone when Safari kept quitting. I went to the Genius Bar at my local Apple Store. I reluctantly agreed to do a factory restore/reboot/whatever on the phone. This upgraded me to iOS 6.1.2, and I also agreed to start using iCloud to back up at least my contacts. I manually sync'ed specific apps and music that I wanted, and it's running great. It's actually running very fast, although I decided to only sync about half the apps I had because I hardly used most of them.
Because I did not restore from a previous backup, there was still the problem of getting my contacts back. After hours of trying to figure out how to manually view data in some of the many backup files, I finally decided to try the iBackupBot software (http://www.icopybot.com/itunes-backup-manager.htm). To my surprise, it worked perfectly and made it easy to see all files, data, etc that were on my previous backup. I was able to save my list of over 100 contacts. Because of the format, I manually added the contacts I wanted back into my phone. It took a while, but I was just happy to be able to successfully retrieve this data from the backup files!
I didn't think I'd say this, but so far I like the newest iOS version and don't seem to notice a battery capacity dropoff. I haven't had further contact list problems yet, and if I do, it should be backed up on iCloud now anyway.
In conclusion, I'm sorry to say that the best option is to do a full restore of the phone and upgrade the iOS anyway. Also use iCloud to at least back up your contacts. If you didn't recently backup your phone in iTunes, then you're probably out of luck in terms of getting contacts back. Also, you'll have to come to terms with losing settings, photos, etc when you restore to factory defaults. Fortunately I got over it pretty quickly. Still though, Apple really needs to look further into how and why this happened!