Might be related to the "keep shuffle status" thing, but probably not. Hitting the button multiple times does not help.