Somebody else put the solution to this into better words than I did so I copied it below from
http://www.pocketpcmag.com/_archives/may00/tips.htm so all credit to them :
"Whoops! Fortunately, the fix is easy. What you probably did wrong was to set up a "new partnership" after you reset your Windows CE device. Your old backup file is only good for your old partnership. Do another full reset of your device. This time, when you put the device in the sync cradle, say "No" when ActiveSync asks you if you want to establish a partnership. This sets your device up as a "guest." Now go do your restore and all will be well."