It needs "h.264 base profile" and probably 800 pixels wide or less. Fortunately I found a great utility (and its free) that will convert just about any video file into the perfect Evo video: "DVD Catalyst Free for HTC Evo". It couldn't be easier to use.There are no options or settings. You just drag and drop the video you want to convert onto it and click the button to start it converting. It works perfectly every time!
I've been so impressed that I went ahead and purchased their non-free DVD Catalyst product for other conversion needs. Here is their home page: Tools4Movies, Official home of DVD Catalyst -- highly recommended!