Well… did you solve your problem?

I am not very well-acquainted with gstreamer, but I found that you can also use it to hardcode subtitles as well. Gstreamer uses a sort of pipeline to apply filters, and takes some getting used to. You can use the command-line gst-launch to set up such a pipeline if you don’t want to bother with a Python or Perl script:
The above command works for me on the test xvid file I linked before (you have to have libgstxvid.so installed on your system), and you can customize the textoverlay further with options covered in the docs. In fact, you could do both the subtitle overlay as well as the image overlay all with gstreamer.

Not yet, still trying things though. I didn't get much chance to look at it yesterday as I had other things to do.

Not sure whats up with MEncoder not working. FFMPEG and imlib2.so works but isn't terribly practical so I'll see what else I can find.

I'll try and have a play with gstreamer today and see what I come up with.