These related threads brought me to the video4fuze solution which allows video to be converted for Sansa Fuze on ubuntu. Confirmed the conversion myself.
http://forums.debian.net/viewtopic.php?p=286477
http://ubuntuforums.org/showthread.php?t=827693&page=4
http://code.google.com/p/video4fuze/
Hope this helps.
