Are you selecting the option to restore from another computer? That's the path you'll need to take, since the reinstall of Windows and OneCare means that the older backups are from "another" computer.
You may want to try the following - on the newly restored PC, configure backup in OneCare to backup a small set of data only and point it to the network location where the old backups reside. Once configured, run the backup. Then use the custom restore option to select the older backup set. And, after the restore has succeeded, reset the backup plan to the desired settings for what and when (and where).
If you are still unable to restore per the above, please contact support.
How to reach support (FAQ) - http://forums.microsoft.com/WindowsOneCare/ShowPost.aspx?PostID=2421771&SiteID=2
-steve