Eu encontrei a solução e enviei um erro para isso: link
Foi causado pela maneira como o LTSP abre aplicativos locais: o LTSP define uma propriedade X contendo o comando e os argumentos, que são lidos no cliente e depois executados.
/usr/bin/vlc --started-from-file %U
é substituído nos clientes por
xprop -root -f LTSP_COMMAND 8s -set LTSP_COMMAND "/usr/bin/vlc --started-from-file %U"
Mas isso usa uma codificação de 8 bits. Se você alterar "8s" para "8u", ele usará uma string unicode UTF-8, que parece resolver o problema.
O arquivo que precisa ser alterado é:
/opt/ltsp/i386/usr/bin/ltsp-genmenu