Yes, I tried restarting many times after cleaning up.
In addition to the installation fix above, I found I had to do one more thing on both boxes - delete the old dbus session entries.
Until I did that, I kept getting:
from anything that tried to import dbus.
dbus.exceptions.DBusException: org.freedesktop.DBus.Error.NoServer: Failed to connect to socket /tmp/dbus-GitKDdcsz0: Connection refused
So, here's the complete solution just in case anyone else runs into this frustrating problem:
I only rarely used the two machines that were having the problem, but when I upgrade them I tend to upgrade them both at the same time. It sounds like I had unfortunately upgraded them both at a point in time where the upgrade process was semi-borked.
sudo apt-get install gir1.2-syncmenu-0.1
sudo service dbus stop
sudo rm .dbus/session-bus/*
sudo service dbus start