Steven Noble: The shuffle button is sensitive to the selected sorting on purpose. It shuffle those that rank relatively high on the selected sort order. If you select an order like "orderliness", "brightness" or "random" it picks from all albums though. Might that explain what you're seeing?

If that's the case, maybe the "fix" for this will be to have an option that disables this behaviour and always shuffles from all albums, rather than sensitive to the selected order.