Corrupted synaptic/apt-get database

[Roberto Waltman]

All of a sudden, synaptic shows many of the regular Ubuntu 
packages (m4, slocate, vim, xserver-xorg, tidy, to name just a 
few) as "Installed (local or obsolete)" under the Status panel.

For all these packages I can only select "Mark for removal", the 
upgrade or reinstall choices are greyed-out.

Same with apt-get:

   $
   $sudo apt-get update
   Get:1 http://security.ubuntu.com dapper-security Release.gpg 
[191B]
   Get:2 http://us.archive.ubuntu.com dapper Release.gpg [189B]
   Get:3 http://us.archive.ubuntu.com dapper-updates Release.gpg 
[191B]
   Hit http://security.ubuntu.com dapper-security Release
   Hit http://us.archive.ubuntu.com dapper Release
   Hit http://security.ubuntu.com dapper-security/main Packages
   Hit http://us.archive.ubuntu.com dapper-updates Release
   Hit http://security.ubuntu.com dapper-security/restricted Packages
   Hit http://security.ubuntu.com dapper-security/main Sources
   Hit http://security.ubuntu.com dapper-security/restricted Sources
   Hit http://us.archive.ubuntu.com dapper/main Packages
   Hit http://us.archive.ubuntu.com dapper/restricted Packages
   Hit http://us.archive.ubuntu.com dapper/main Sources
   Hit http://us.archive.ubuntu.com dapper/restricted Sources
   Hit http://us.archive.ubuntu.com dapper-updates/main Packages
   Hit http://us.archive.ubuntu.com dapper-updates/restricted 
Packages
   Hit http://us.archive.ubuntu.com dapper-updates/main Sources
   Hit http://us.archive.ubuntu.com dapper-updates/restricted Sources
   Fetched 3B in 0s (4B/s)
   Reading package lists... Done
   $
   $
   $ sudo apt-get install --reinstall vim
   Reading package lists... Done
   Building dependency tree... Done
   Reinstallation of vim is not possible, it cannot be downloaded.
   $

Any ideas on what could cause this and how to restore normal 
behavior?

Thanks,

Roberto Waltman.