It is likely that the contacts data was restored to an alternate location since a newer version of the file existed on the PC already. You should find files that were not restored in an alternate location on the PC, typically a new folder on the C:\ drive perhaps called Windows Live OneCare Restore or similar. If that doesn't appear to be the case, please contact support.
How to reach support (FAQ) - http://social.microsoft.com/Forums/en-US/onecareinstallandactivate/thread/30400b52-7f26-4ba0-bc18-17e305329d90
I don't use Windows Mail or Windows Contacts, so I can't tell you what the contacts file is or confirm what happens in a backup/restore.
-steve
Microsoft MVP Windows Live / Windows Live OneCare, Live Mesh, & MS Security Essentials Forums Moderator