minitube на Fedora 23

Хз как в Федоре у него с зависимостями, посмотри есть ли пакеты типа phonon-backend-vlc или phonon-qt4

а что с rpmfusion у тебя?

Подключен, но там этого пакета нет.

phonon-backend-vlc установил, но это ничего не изменило, phonon-qt4 в репозиториях нет.

https://bugzilla.rpmfusion.org/show_bug.cgi?id=3696

Youtube has changed their API and this package will not work until some has time to update it to version >= 2.4