I'd been reshuffling by turning the shuffle off and then back on. This does lose track of which songs have already been played.

Sounds like a bug to me.

Peter