Comment 13 for bug 152820

I experienced the very same problem.

The solution was to remove any evms-packages.
Even though https://wiki.ubuntu.com/Evms states, that it recomends removing emvs during the update process, I was not aware.