I just got the Fuze+ today, and I got Handbrake to work on my first try. I converted an MKV to MP4.
Handbrake 0.9.4. Sansa on the latest firmware (1.32 I think).
I used the Legacy|Classic profile on Handbrake with the following settings:
Picture | 320x240
Video | MPEG4, 25fps
Audio | AAC, 44.1 samplerate, 128 bitrate