In the new xbox music, when I hit the shuffle/play all, it does not load all my songs as random, only some of them. But I can still go play them manually by selecting artists, etc!
No.
Xbox Music app in it's current, disappointing, state will only play a random selection of I believe 100 songs.
There is absolutely NO way to queue more than 100 songs at a time.
It's awful.