I'm not using Mala yet, but if it's starting on the same track (presumably the first in the folder?) each time, you might be able to work around this by putting a short (say, 2-5 second) "blank" track at the top of the folder. Perhaps that would play, then go on to random tracks?
If the random track selection is broken entirely, and not just for the first track, feel free to disregard my rambling.
