Is this with the Apple Music app on Apple TV and an Apple Music subscription,
or is this with the Computers app on Apple TV and Home Sharing,
or is this with AirPlay?
Separate from Shuffle, there is a control for Repeats (repeat playlist/album, repeat song, repeat off). Please check that as well. Apple Music app on Apple TV - Apple TV user guide - Apple Support
Some upcoming albums may have an early release of one selected track (or two). Then the “coming later” tracks would be grayed out (and skipped).
I’ve noticed for myself, that a few albums in my Library sometimes may get hosed and show incomplete albums. Deleting and re-adding that album to my library fixes that.
Does this happen for all albums (that you have tried), or just some albums?
Can you mention an album that has this issue, for me to try on my setup?
If you have other Apple devices to play this on, does that behave the same or different?