I think this is the problem. The framerate. Your PS3 will be set to braoadcast to your TV, a standard North American NTSC picture.
I have no idea about Xilisoft, or how it works, as I just play .avi's straight off my PC. I'm thinking, though, that maybe the program is somehow forcing the re-encode to 29 fps. Maybe see if this is possible.
I could be wrong, but that is a big framerate difference, and the only real noticeable difference between the two examples. Are all the mp4 episodes that you have re-encoded giving you grief? If so, maybe start here.
EDIT: if the files are a lower resolution, that what you are re-encoding them to, maybe it is forcing this high framerate. Just and idea.