Might want to try Video4fuze, a video converting program written by a former member here after he too encountered frustration in converting videos that would play sucessfully on his Fuze player.
I haven’t used it myself, but many, many people who have recommend it highly.