Wjosten,
You are absolutely correct, they are very much apart of the backup. I lost all my contacts and did the same thing as you, restored a previous backup. Upon completion of the restore, all my contacts were there. Like you, after 30 seconds, mine too erased. I tried to mess with iCloud with no luck, after re-establishing connection with either wi-fi or cellular, my contacts erased.
I tried several times and was able to finally get my contacts copied over from the restore, here is how but only works if you have the restore available with the contacts still present.
1. Restore from the previous backup (you must watch your phone because you have to be ready for the next step)
2. When your phone restarts, immediately place your phone in "airplane mode" to stop it from connecting to the cloud and wiping away your contacts. (Your contacts will remain until airplane mode is turned off)
3. Within iTunes, search for and download "My Contacts Backup" which is FREE and does not need to connect to the Internet to work.
4. Within iTunes, under the iPhone, navigate to the App's tab and find "My Contacts Backup" and click the install button to have it installed onto your phone.
5. After installed, run the "My Contacts Backup" and follow the prompts. Do not change any settings, they are already properly set up. After it copies all the contacts, it is ready to e-mail out. Email them to an address you can get on your phone.
6. Turn off airplane mode (this will delete the contacts as said above but we have a backup.)
7. Open the e-mail and click on the attachment. Follow the short steps and all your contacts will re-populate.
If you are like me, this fix also took care of my iMac and iPad contacts. I have all 400 contacts back. I hope this helps if you haven't found a fix or anyone that finds this page in the future. While trying to fix this, I stumbled across software that was over $100.00 to fix this problem. This is the free way
FYI - I had the iPhone 5 running 6.0.2
Good luck,
Reed