I kept getting this error-
The package libnautilus-extension1a needs to be reinstalled, but I can’t find an archive for it.
This prevented my Ubuntu 12 from installing anything new
This was the final solution-
sudo gedit /var/lib/dpkg/status (you can use vi or nano instead of gedit)
Locate the corrupt package, and remove the whole block of information about it and save the file.
In my case the package libnautilus-extension1a was corrupted so I removed all info about it, and voila now the reinstall is working