Please check out our latest release, Build 763. While the changes in 1.8 were intended to make the album browser’s play options more consistent with other screens, we know that shuffle was not actually selecting content from across your entire library.
This has now been resolved, and it’s once again easy to play a completely random selection of music from your library.