So, it looks like the issue only effects people upgrading to 16.04, as opposed to doing a clean install. If that's the case, I've had similar issues when trying to upgrade PHP to version 7 on Ubuntu 14.04. The solution ended up being a re-installation of one of the packages, although I never wrote down which one, and was just glad to have got my system back to normal so I could get back to work. If it was me, I'd start a new thread over at ubuntuforums.org.
