Contacts and the other Apple data like calendars, reminders, etc. are not part of a backup. They are stored on icloud's servers. All you need to do if you have a new device is to go to Settings>icloud and log into the same account. All that data will suddenly appear on the device. A backup stores other data, like camera roll photos, game data, messages, ringtones, and other data.
Now about a backup...
If you get the error "Backup not successful" and you've tried deleting the last backup and trying to back up manually without luck, try the following test: Go to...
Settings>iCloud>Storage & Backup>manage Storage, tap your device name in the Backups section, then look under Backup options. Turn off all apps from backup and then do a manual backup. If that doesn't work, then this post will not help. If the backup works, then go back to the app list and turn some on and try another backup. If successful, keep repeating these steps. If it fails at some point, then try to zero in on the one app that seems to make the backup fail. (I had this problem and found one app failing, probably due to a corrupt data file.)
This process will take time, but if a backup works with no app data being used but clearly fails with the original settings, then somewhere in the mix of apps is a "bad" one.