I also have a Fuze (mine is a V1) and was having the same problem. In addition to the delay, same as yours, I was also getting some sort of electrical noise, like a quick faint crackle, when changing tracks. I still get the crackle thing sometimes.
What helped me with getting rid of the delay, and most of the noise was enabling cache and ram....and turning of crossfade. (settings/playback settings/crossfade/enable crossfade/off). I have no idea why truning off crossfade helped, but it did.
Try it and see if it works for you. Good luck