Stop your automatic updates service.
Rename "C:\WINDOWS\SoftwareDistribution\DataStore\DataSto re.edb" to "DataStore.old"
Start automatic updates service
Go to windowsupdate and try it again.
*********
Also check registry to make sure you are not disabling Windows Update access.
Here's a link to see what I mean:
http://www.pctools.com/guides/registry/detail/441/