icloud says no backups available

This is Apple's documentation on that error message (from http://support.apple.com/kb/TS4036):

"This occurs during initial setup if the Apple ID entered has no backups online, and you are attempting to restore from it. This can occur if you have no backups, you are attempting to restore a Backup created with a newer version of iOS than you are attempting to restore to, or if you have multiple accounts, and you are using the wrong account in iCloud. If you have multiple iCloud accounts and you are attempting to restore from the wrong one, you should back up a few steps in setup and enter the correct Apple ID."

If you updated your device and continue to get this message, then you either have multiple iCloud accounts and are signed into the wrong account, or (unfortuanately) your backup was not successful and it isnt' there.

You might check iTunes to see if you may have a backup on your computer you could restore to. It might be old, but may be better than nothing. To check, open iTunes, go to Preferences>Devices and check the backup list.

How did you backup?

Is your phone running the same level of iOS as the one you backed up, or higher? If not you won't see the backup until you update it. Also make sure you signed into the iCloud account you backed up to.

If I am not mistaken, if backup is not compatible, that is what message going to say, and update does help. That time it sounds like backup is not there.(Randers usually is way better then me so my apologies if I am wrong). I d be curious to find out at who you ******* right now, - yourself? You can see and check if back up is available in settings - icloud on storage and back up page. You d need to update anyway if Randers is right. And when you sign in to cloud check it. Your contacts still may be in the cloud, check icloud.com.