Since you've already run Tune-up multiple times without solving it, I'd do the following:
1. check the PC date and time
2. Modify the tune-up schedule to run it at a future date
3. Reset the OneCare database with this tool:
http://www.microsoft.com/downloads/details.aspx?FamilyID=4bc2594b-95ab-4235-b5b8-41656b38480f&DisplayLang=en
Note that using this will require you to reconfigure settings for OneCare including backups, schedules, and firewall exceptions.
If none of these help, please contact support.
How to reach support (FAQ) - http://forums.microsoft.com/WindowsOneCare/ShowPost.aspx?PostID=2421771&SiteID=2
-steve