Comment 29 for bug 1564156

Unfortunately, this broke my installation completely. Chroot-ing into the broken installation and running the updates fixed my problem. Here's the walk-through if anyone is still stuck: https://toroman.wordpress.com/2016/04/26/getting-out-of-a-broken-ubuntu-16-04-system-after-an-upgrade/