I use ncmpcpp (a client for mpd) and it does the same thing. I've never had any issues with its shuffling; it just works exactly as I would expect it to for everything.
On a sidenote, mpd + ncmpcpp is a killer combination for playing and managing music. I can only recommend that to anybody geeky enough to use a CLI music player :)