I haven't had much luck with quality / artifacts yet, but both mencoder and ffmpeg run fine on the N900. Can't remember if they were in repos or not, but a quick Google should help. You could probably run them in Easy Debian too.
You can do a lot on the command line with mencoder / ffmpeg, but they're not full on linear video editors.
The last video I converted / edited with mencoder went at about 7fps.
I have FFmpeg version SVN-r19352-4:0.5+svn20090706-5 and MEncoder SVN-r30099-4.2.1.
Hey dantonic, did you find a solution to this? I had the same problem on Lucid both with mplayer/mencoder and ffmpeg and came across your post. I suspect there was a problem with libavformat which is used by both applications and probably also the tools that you used to edit the videos.
I discovered that mplayer selects the wrong format and for some reason it makes the right selection when you pass it
-lavfdopts format=<anything>
For ffmpeg the only solution I could come up with was to build a newer version from source (I picked 0.6.1) In case you haven't done it before, just download the tarball, untar it, cd into the dir and type:
