This is fixed in Feisty (probably since Dapper or Edgy). ** Changed in: rhythmbox (Ubuntu) Status: Confirmed => Fix Released -- Shuffle mode is dumb https://launchpad.net/bugs/33868