[vadblm]

(Ubuntu, Mint) устраивают на экране эпическую полосатую кашу, в которой ни черта не разобрать. »

Попробуйте добавить в загрузочные опции nomodeset или radeon.modeset=0

даже аппаратный декодер видео »

Быть того не может, поскольку радеоны на линуксе могут аппаратно декодировать видео только посредством XvBA, а для его использования необходимы следующие условия:
— карта HD 4000 или новее;
— проприетарный драйвер Catalyst;
— плеер с поддержкой XvBA.

Как минимум одно условие у вас не выполняется (видеокарта явно старая), да и драйвер у вас наверняка опенсорсный radeon. Да и вообще,

на 720p тормозить начинает, не говоря уже про больше »

говорит о том, что декодирует CPU, причём слабый. top не смотрели при проигрывании? К примеру, при использовании vdpau даже GeForce 9300 в лёгкую справляется с 1080p, при этом цпу загружен на 2-5%. На всякий случай, приведу условия для аппаратного декодирования видео при помощи nVidia:
— карта GeForce 9-й серии или новее (часть GF 8-й серии тоже может, но там нужно смотреть — часть может, часть нет, начиная с 9-й — поголовно.Выяснить возможности своей карты можно при помощи утилитки vdpauinfo);
— проприетарный драйвер nVidia;
— плеер с поддержкой VDPAU;
— видео в поддерживаемом формате (изначально поддерживается видео, закодированное в MPEG-1, MPEG-2 (DVD), WMV3, H.264, VC1 (Blu-Ray). Начиная с GeForce 200-й серии добавлена поддержка и кодеков MPEG-4 (DivX/Xvid)).