I have a freshly installed 12.04. Running the update manager gives me this:
I even changed my update server ( by selecting "Select Best Server" ). Checking around the net gave me no solutions. I have also seen similar questions around but none helped.
Updating from terminal gives me this
I don't know how but some how it started to work. :)
I can't tell what made it work but here is my current system status when it started to work.
The Server was set to
Main Server
There were no 3rd party repositories.
The MAIN part is some how make the system auto check for updates
That solved my problem and should maybe solve your problem too.