Да верно, totem. Попробовал переустановить gstreamer, totem как раз оказался в зависимостях. Это не помогло.
Послушал вашего совета, ушел на VLC, там проблем не бывает.
Специально установил тотем на посмотреть. Файлы типа avi, mpg, mkv воспроизводит ровно, никаких артефактов. Похоже на дебианопроблемы.
Тотемом не пользуюсь, хватает mpv
Добавлено:
Поторопился, некоторые mkv воспроизводит криво. Ругается вроде на ваапи. Перезагрузился в хорг сессию, проблемные видео заработали, но при ресайзе или перемотке начинает содом&гоморра.