On Kubuntu I'm using VLC http://www.videolan.org/vlc/ for transcoding videos to a format that's suitable for the N8x0.

VLC has lots of features, a GUI and besides transcoding to a file it's even possible to stream the video directly to the N8x0 while transcoding.

I have added a tutorial with suitable VLC settings to the german N800 wiki. The article is in german, but there are quite a few screenshots which should be pretty much self explanatory.
http://www.n800wiki.de/pmwiki.php?n=Main.DVDStreaming

Basically I'm encoding to .asf container (only .asf containers are properly working for streaming to the N8x0. But if you are not interested in streaming probably another container will also do). Video codec is mp4, with bitrate well below 1024 but above 512 kbit/s and scaling down the video to 50% to 75% of the N8x0 screen resolution (this really depend on the compexity of the video). Audio codec is mpga, stereo, 128 kbit/s.

For playback of the video/videostream on the N8x0 I'm using mplayer. With the softvol option to bump up the volume and the aspect option to correct the aspect ratio (if neccessary).

So far I had no problems at all with this setup. And I already did transcode + stream a whole lot of DVDs to the N8x0 this way.