The MKV container has new features that are problematic for conversion to AVI, one of which is variable framerates (VFR). Neither mencoder nor any converter I know of will convert that properly to AVI. Too, some people still use crappy muxers like VirtualDubMod to make MKVs that play on PCs, but not anywhere else. Lastly, mencoder itself isn’t foolproof, nor is the libavcodec library it relies on to decode the input files.
In short, not all media can be converted. When you run into something that doesn’t work, it’d be helpful if you can snip a sample and post it online if you have the tools to do that, so others can examine it. Otherwise, just shrug and move on.
The good news is that the AVI format is dying out, just as VCD/SVCD before it. The next PMP you buy will use MP4, and conversion for them will be much more straightforward, if needed at all.