Yeah, it means "ubuntu" font is not shipped with 10.04. And its used in my default config. Try to change it to some other font from fc-list (for ex. Arial, preferably without spaces in name because there is bug in PMS with font names escaping) and see if it makes a difference.
Very strange. Looks like severe bugs on 10.04 version of mencoder. Maybe other 10.04 users can confirm / deny these issues. 11.10 works fine for me, no font problems. Do you try system reboot? Simple, but sometimes very effective Whats your system RAM size?
1. My bad. I misread your explanation and thought that "mencoder_remux_mpeg2 = false" gave you problems. Please try decreasing transcoding buffer down to 200 Mb and try remuxing again. 2. Can you upload sample of this file to mediafire or send me PM link?