Figured it out. VertSMS depends on gtk/hildon which depend on gobject.

Uninstalling every python package then installing python-minimal left me with import errors (obviously). After removing that and simply doing a "apt-get install vertsms" I see that python-gobject is pulled in with everything else.

In short. "apt-get install --reinstall vertsms" should do the trick. That, or "apt-get install --reinstall python"