If not, is there a way to convert them?
It plays .avi only. You could try the “Any Video Converter” to convert to .avi. The free version works fine for just converting between formats. Here it is.
And then I believe you have to format it for the Fuze.
Use Video4Fuze. http://code.google.com/p/video4fuze/
Oh, I actually meant MP4 music files. I already converted them, but thank you both for answering.