there is a free program out there called super that will convert just about anything to anything else. there is also a divx player out there somewhere too. I have used super and haven't had any problems playing video on the e62. you might be using the wrong video codec or something unsupported on the phone.
Are you converting the converted file? Convert from the original file. Don't use the nokia converted file to have super convert it, convert the original file with super.