DOES ANYONE KNOW HOW TO FIX THIS PROBLEM?
Initially, restart was hanging with the same messages as PedroC4 or RikM.
Now its getting stuck in a start Job:
/dev/sda1: recovering journal
/dev/sda1: clean, 291978/4128768 files, 2303300/16514816 blocks.
Starting Hold until boot process finishes up...
There are known problems when upgrading Ubuntu from 14.04 to 16.04, and some suggested fixes can be found here: http://askubuntu.com/questions/760825/cannot-boot-system-due-to-start-job-running-for-hold
Now, the various fixes says "Go in your safe mode by hitting SHIFT key or ESC."
One problem is that I can't find the right moment during restart to hit SHIFT key or ESC. I.e., Hitting ESC repeatedly from the beginning usually displays random startup messages. Only once did it get me into the safe mode selection menu.
In any case, hitting Ctl-Alt-F2 I give me the login prompt. From there I was able to sudo to root, and tried to follow the various fixes. Unfortunately none of them fixed the hang problem.
Now, when I reboot I just see:
/dev/sda1: clean, 329795/4128768 files, 2565580/16514816 blocks.