I found that the Veoh Player actually CAN work on Ubuntu, with the help of the infinitely compatible Wine. But to call that trivial would be a little on the light-hearted side, and entertainment is a serious business. So, I decided, it is time for a little guide.
Read the many things to do here
In order to never think about what to do next again (if you don't mind sitting in front of a screen all day), you need:
* Ubuntu Feisty Fawn & Wine [Please install this via Synaptic, apt-get, ...]
* Mozilla Firefox for Windows, Version 2.0.6 (Yes, for Windows) [Download]
* Veoh Player for Windows, Version 126.96.36.1993 [Download]
* A Veoh.com account [Create]
* Approximately 50MB disk space (plus several GB for videos)