Morisson, bezbo,
Вы правы у них свои отдельные библиотеки и бинарники.
Но все же проблема оставалась идентичная. Также я заметил что перестал работать skype. Все эти три приложения связывало то что они работают на i386 архитектуре. Поэтому мои действия были следующими:
sudo apt-get purge *:i386
sudo dpkg --remove-architecture i386
sudo reboot
После перезагрузки:
sudo dpkg --add-architecture i386
sudo apt-get update
sudo apt-get upgrade
После установил wine, teamviewer и skype. Проблема исчезла.