FoxtrotZero, having been in your position fairly recently, I suggest you try Video4Fuze.
I had been trying multiple solutions, but Video4Fuze turned out to be a simple, one-stop solution. It even fulfilled my greatest hope… it was free!
Here’s the discussion with the download links:
http://forums.sandisk.com/sansa/board/message?board.id=sansafuse&thread.id=31437
Once the video has converted, I can easily just drag-and-drop it into the Video folder on my Fuze. The only video issues I have now are related to how the Fuze version 2 deals with fast forwarding, and that is independent of the conversion software or the file itself.
