Olha galera, praticamente não ocorrem mais esses problemas com relação ao nome diretório e com a codificação da legenda.
A questão é que pode existir algum erro na codificação xvid do arquivo avi, pois percebí que nem o Avidemux que é um cavalo de batalha consegue encodar um vídeo .avi para DVD em MPEG-PS A+V se ele encontrar alguma inconsistência. Então a minha dica é com o próprio Avidemux (que está no repositório do Ubuntu, pra quem não conhece) reencodar o avi em Xvid. Vou explicar, é bem simples.
1º Abra o Avidemux, clique em abrir e escolha o arquivo.avi que quer encodar. Vai aparecer a seguinte mensagem:
"Index is not up to date
You should use Tool->Rebuild frame. Do it now ?"
Clique em 'sim' e espere terminar.
2º Vá na coluna da esquerda, em 'Video' e onde está 'Copy' escolha 'MPEG-4 ASP (Xvid)'. Em 'Áudio' deixe em 'Copy' mesmo.
3º Se quiser embutir alguma legenda pra poupar trabalho ao DeVeDe quando usá-lo pára criar a iso, pode fazer isso (se não vá para o 4º) indo em 'Video' na aba 'Filters'. escolha 'Subtitles' e escolha 'Add srt/sub subtitles to the picture'.
Agora escolha o arquivo de legenda .srt ou .sub e escolha a fonte (ttf) que deseja utilizar (você pode baixar uma na internet ou usar uma das fontes do sistema que ficam em /usr/share/fonts/truetype. Eu gosto da /usr/share/fonts/truetype/ttf-dejavu/DejaVuSans.ttf).
Escolha a cor da legenda, pode ser qualquer cor. Em encoding escolha 'Latin-1' e escolha a posição e o tamanho que deseja que a legenda ocupe (no tamanho recomendo entre 20 e 24, dependendo do tamanho da TV, maior que 24 fica fora da tela e menos que 20 fica pequeno demais, vá de 22 que é bom em qualquer TV).
4º Pronto, agora é só clicar em salvar e escolher o nome do 'arquivo'.avi. No final ele estará até menor do era antes e a qualidade será a mesma, não notei diferença, porém ele funcionará com o DeVeDe que é o que queremos.
O DeVeDe agora vai conseguir encodar o vídeo colocar a legenda e criar a iso com menu e tudo tranquilamente.
Recomendo também o DvdStyler (também no repositório) que não é melhor para encodar, mas tem bem mais opções para poder criar menus de capítulos. Eu uso o DeVeDe para transformar em mpg e o DvdStyler para criar a iso com um menu maneiro.