Binary package hint: banshee
The shuffle by artist/album options are always greyed out, I've never been able to use them. There's no indication as to why and the documentation is somewhat lacking on this point. At the very least this is a minor UI bug (why show these options if they don't work?).
(jaunty version 1.4.3-3ubuntu2