OK I had this problem earlier tonight - Iphone 4 - IOS 5.1.1 - I went to send a text message, crashed a few times, shut down and restarted, contacts were gone. I BELIEVE I had icloud on ORIGINALLY BUT when i went into the settings on my phone everything was ON but the icloud backup at the bottom tab was switched to off..... I went to icloud.com, logged in, there were 171 contacts there (I have 867 contacts on my phone).
However, I was able to get my contacts back. All of them. Heres what I did - This is going to be a long winded detailed instruction on how I got my contacts back, so sorry for the novel.. This might not work for everyone, but it worked for me.
FIRST OF ALL, before I go on, I will say that my itunes has always been checked to backup to this computer (I don't know if this is WHY i was able to get my stuff back, but I believe if it wasnt for that i would have been screwed.
OK, I believe you have to do this BEFORE YOU PLUG IN YOUR IPHONE TO SYNC WITH ITUNES (if you have already done this it might not work - cant confirm or deny, just speculating)...... Since itunes automatically syncs and backups, i think this is why you have to do this step plugging in your phone to your computer) . Also, this will only backup the last time your iphone was synced (luckily mine was set to sync wifi so it had done it 2 days ago so i did lose the last 2 days of texts/photos/etc. BUT i got my contacts back up until that so i am more than cool with that)
On your computer go to your backup folder for itunes on your computer. Google this location for mac, but for PC:
Windows XP:
\Documents and Settings\USERNAME\Application Data\Apple Computer\MobileSync\Backup\
Windows Vista or Windows 7:
\Users\USERNAME\AppData\Roaming\Apple Computer\MobileSync\Backup\
(Replace USERNAME with your personal account name)
There is a folder that is in the backup folder that is a long number and letter named folder.... If your itunes backs up to your computer that is all the info from the last backup. COPY THAT FOLDER and PASTE IT ON YOUR DESKTOP.
Then plug in your iphone. Let it sync. Then in itunes go to where it says backups... the "restore from backup is prob unclickable (mine was). Click on backup - let it backup.
Then go BACK to that folder where the orig backup was (USERNAME\application data\ apple computer\mobilesync\backup). now take that long number/letter folder OUT of there... just cut and paste it somewhere else OTHER THAN YOUR DESKTOP so you won't get it confused with the previous folder.
Now take the folder on your desktop (the orig backup) and Copy/PASTE it into where the itunes stores the backup data (USERNAME\application data\apple computer\mobilesync\backup).
In Itunes, go the "restore from backup" button should be clickable at this point. Click it.
It should restore from the OLD backup BEFORE the screwup happened providing you havn't synced. At least mine did.
Hope this helps someone.
BTW If you DO get the contacts back, you should prob back them up to another program just in case. personally I used a program called memova - you can sign up for it at my.memova.com for free and download the app on your phone, sync, then export to a .csv (excel/outlook) file.