I finally discovered a solution, though, so it's sharing time. Note that this is probably unnecessary if you just want to watch video podcasts, because gpodder works fine for that. For non-podcast video, you almost always need to do a conversion.
(Using Ubuntu, version
For this meal, you will need these ingredients (aptitude install ..):
(every gstreamer plugins package you can find in main or in universe / multiverse)
The avidemux-cli package is optional; handy if you want to convert a whole directory full of files. Note that you are going to install vlc, because it is one of the few players that will reliably play back these files. You want it so you can test your output files before installing them on your ipod, but it may be considered optional.
- Open up the avidemux GUI, and open the file you want to convert.
- Select menu item Auto > IPOD
- Confirm that video is being encoded with XVID4. Optionally change the video bitrate to 1024 through the Configure button.
- Audio encoding will still show "Copy". Change it to "AAC". Confirm through the configure button that the bitrate is 128.
- Confirm that Format is MP4.
- Save. Encoding will begin.
Test the converted file in VLC, making sure video isn't crappy and audio exists.
Now copy it to the iPod. You need gtkpod-aac installed for this, or you will get errors saying "compile gtkpod together with yadda yadda". The package gtkpod-aac contains a binary that is already so compiled. You can simply plug in the iPod, choose your model from the supported list in gtkpod, find the iPod in the tree at the left, pick "video inbox", and Add File there to add your file. Save to copy to the ipod, and Eject the ipod.