I tried the ubuntu live cd and in their package system was vlc available.
I installed it through their system (only 0.8.2, I think) and it worked well. I don't know with which options it's compiled for ubuntu, but playback of divx/mp3 video files worked, I tried nothing else.