Same happened to me when after a full restore, i chose "setup as new" instead of "restore from backup". I think the problem is that the name chosen for the iphone was the same as before the restore, in fact itunes has completely overwrite the old backup with the new -empty- one, automatically without ask me. Luckily i usually keep all my bakups in double copy on another disk, iphone backups included.
Anyway i don't like this way to take backups, i think Apple needs to completely revise the backup and synchronization system.
Why, in example, there is no way to do a selective backup? Every time synch all that stuff is a mess, why can't backup only some apps or some savegames? or maybe Text messages in text files? And so on, but i'm going off topic, sorry.