The container format (AVI/MPG/MP4/MOV) is only part of the video's type.
- Video Codec
- Audio Codec
- Sampling Frequency
If any of those parts is "out of bounds" for a specific player, then the video file won't play on the player (or will play with a lot of issues if you try to use it in a video editor), even if it's of the correct container type. When you use a converter for a specific platform (such as for the PSP or DS or ipod) or to a specific format, it doesn't convert just the container, it formats every part of the video to certain specifications so it'll play properly, which is partially why it takes so long to convert.
So PMP can play some AVI files fine, and others it can't.