After copying a presentation from my laptop to my desktop box (which’s running OpenOffice.org 3.1.1) the embedded AVI videos didn’t show up anymore. It turned out that the JRE was missing gstreamer.
The solution
sudo apt-get install ubuntu-restricted-extras