Se você estava usando o player HTML 5 do YouTube (como sugere o "nunca perguntar novamente" no pop-up), a configuração de tela cheia é gerenciada pelo Firefox (e, portanto, não tem nada a ver com o Ubuntu ou o Gnome).
Vá para about:permissions
(basta copiá-lo na sua barra de endereços), selecione www.youtube.com
da lista e mude a configuração na caixa Tela Cheia .