installation - Unable to install programmes after upgrade

I upgraded to 11.04 today. I had some problems when the system froze with 2 minutes to go; I was forced to do a hard reboot, but the system appeared to work OK. (described here: https://askubuntu.com/questions/40295/distribution-upgrade-froze-my-system)

As the system hadn't been cleaned up before rebooting, I ran Computer Janitor, but had to stop it when I saw it was deleting things I needed to keep (e.g. Faenze icons vanished). Since then I have been unable to install anything via apt-get, Synaptic or Software Centre. I can add PPAs, but attempting to install anything returns the following message:

E: Sub-process /usr/bin/dpkg returned an error code (1)

The only way I can install anything is by downloading the deb and installing manually.

Trying to install with the Software Centre causes a window to open saying "An unhandled error occurred). Clicking on "details" reveals the following:

Traceback (most recent call last):
File "/usr/lib/python2.7/dist-packages/aptdaemon/worker.py", line 961, in simulate
trans.unauthenticated = self._simulate_helper(trans)
File "/usr/lib/python2.7/dist-packages/aptdaemon/worker.py", line 1085, in >_simulate_helper
return depends, self._cache.required_download, \
File "/usr/lib/python2.7/dist-packages/apt/cache.py", line 226, in required_download

pm.get_archives(fetcher, self._list, self._records)
SystemError: E:I wasn't able to locate file for the rec-applet package. This might mean >you need to manually fix this package.

However, when I try to repost the problem, another window opens with the title "Problem in aptdaemon" and

The problem cannot be reported:

You have some obsolete package versions installed. Please upgrade the following >packages and check if the problem still occurs:

python-gobject

EDIT - I tried Jordy's solution. When I then checked for local or obsolete packages in Synaptic, one was marked in red and marked for removal (rec-applet). When I attempt to remove it, I get the message:

E: rec-applet: subprocess installed post-removal script returned error exit status 1

It's as if that was blocking everything else, but there doesn;t seem to be a way of removing it.

EDIT 2 - I remived the offending package following the instructions here: http://www.khattam.info/solved-subprocess-pre-removal-script-returned-error-exit-status-2-error-2009-08-04.html

I feel a bit dirty but it did work, and no need to reinstall the OS.