Today we had a customer who had somehow broken his apt package manager doing an upgrade from the looks. I googled and found the same error in many places, most resorting to reinstalling or purging the package to clear it, or reinstall.
The error looked like this

3 upgraded, 12 newly installed, 1 to remove and 14 not upgraded.
3 not fully installed or removed.
Need to get 0B/2,770kB of archives.
After this operation, 4,067kB of additional disk space will be used.
Do you want to continue [Y/n]?
E: Could not perform immediate configuration on already unpacked 'util-linux'.Please see man 5 apt.conf under APT::Immediate-Configure for details.

Because the package in question was util-linux , we were unable to purge or remove that package we had to find an alternative way to get around that.

To make a long story short, i took a backup of the system before touching anything in case i broke it (always a good policy), then ran the following

apt-get -f install -o APT::Immediate-Configure=0

Bingo, this fixed everything. Once that dependency had been installed correctly i upgraded and finihsed the config of other packages as per usual, and apt-get/dpkg was all fixed.

Should this happen to you on your Rimuhosting server, and you are unable to fix it, just drop us an email.