Pues no queda otra solución visto lo visto. A utilizar la versión de Firefox para Windows, con el Veoh Web player plugin para este navegador.
Instalas con wine:
$ wine Firefox\ Setup\ 3.0.7.exe
E instalas el Veoh Web player plugin:
$ wine VeohWebPlayerSetup_eng.exe
Descargar Firefox para Windows | Firefox 2.0.7 Español
Descarga Veoh Web player | Veoh Web player para Windows
Captura de pantalla funcionando en Debian GNU/Linux Lenny stable:
A día de hoy el software de VeohProxy no funciona. Veoh ha debido cambiar algo en la forma en la que distribuye sus vídeos. Esta práctica no es nueva, Veoh continuamente “mejorando” (ignorando siempre sus usuarios de GNU/Linux).
Parece ser que el problema es que en el nuevo Veoh Player utiliza un nuevo método para generar claves, y los responsables no dan soporte para la antigua forma de descargar los vídeos.
Los desarrolladores de VeohProxy están trabajando para sacar una nueva versión.
Gerkemsm:
I don’t have time to do this right now and probably won’t have during the next few
months. I’ll have to write my thesis. Sorry..
Tendremos o que utilizar wine para ejecutar Firefox con la extensión de Veoh (ver este post), o virtualizar Windows 
Más info (en) | Issue 23: Downloading from veoh no longer works