After upgrading to "PrecisePangolin", this message got printed whenever dpkg wanted to install a package:

dpkg: warning: parsing file '/var/lib/dpkg/available' near line 262698 \
          package 'lightning-extension-locale-hu':
 'Depends' field, reference to 'lightning-extension': error in version: \
          invalid character in version number
dpkg: warning: parsing file '/var/lib/dpkg/available' near line 76038 \
          package 'am-utils':
 'Replaces' field, reference to 'amd': error in version: \
          version number does not start with digit

This got printed a few times, for every package with a weird entry. Apparently /var/lib/dpkg/available got mangled during the upgrade:

Package: lightning-extension-locale-hu
Depends: lightning-extension (>= 0.7), lightning-extension (<< 0.7.*)
[...]
Package: am-utils
Replaces: amd (<= upl102-35)

Bug reports for this issue are usually being closed, so I refered to the suggested practice of clearing the available database:

$ dpkg --clear-avail

And it worked, dpkg installs much quieter now :-)