I know this doesn't help you now but usually it is best to wait for the .1 release of a new LTS (in this case, 16.04.1) before updating from the previous one.

I know this doesn't help you now but usually it is best to wait for the .1 release of a new LTS (in this case, 16.04.1) before updating from the previous one. I did a test upgrade from 14.04 to 16.04 on a workstation that I didn't care about and it was an unmitigated disaster of broken packages.