Yes, the solution for me was to remove those ubuntu-* meta packages, reinstall what I needed by hand then update. Simple things like ftp, telnet, time, etc. had to be reinstalled.

I was kind of nervous on the reboot since a plymouth theme was removed in addition to adding a newer kernel with the amd microcode patch, but it came up fine.