Got an interesting message from Software Updater. After waiting an hour to see if it was transient I went to my 16.04.01 VM to investigate it there:
Ran synaptic and it's perfectly happy. A bunch of updates but it worked ok. I did notice it had to remove a package: libgles1-mesa
Using the magic of a VM, I restored the snapshot and checked again but this time in a terminal:
sudo apt remove libgles1-mesa
Now, Software Updater was also happy - no more partial update message.
I conclude whatever state these updates are in, Software Updater (but not Synaptic) failed to recognize it had to remove libgles1-mesa to resolve whatever it was trying to do.
So if anyone else sees this:
Workaround1: Manually remove libgles1-mesa like I did above.
Workaround2: Use Synaptic and forget about what Software Updater says.
Workaround3: Wait and see if something clears up.