We need more information to help, but shuffle works basically like it always has, as far as I know. Can you answer some questions for us?
1. How is the view you are using structured? Is there any grouping involved? Are you using Panes and Details, or Tiles?
2. How are you starting the shuffled playback? There are lots of ways to play things from within MC, from double-clicking a file to right-clicking and using the Send To menu to Theater View and WebRemote.
3. What shuffle mode are you using, if any, ON or AUTO?
Question #1 is particularly important. If you "drill down" into a set of "tiles", and double click on a song within a view showing only the list of songs on the album (because that's how you get to the list of songs), then it will only play songs within that album. If you want to shuffle play a full genre with a view set up this way, you need to either click Play on the Genre itself (using the pop-over controls), or you need to customize the view and turn on the "Always Show Files" option.
Double clicking a file (with the default double-click behavior enabled) will always play all of the files showing in that view, but not any others that you've already filtered out.