Presume:
- you've unplugged AppleTV, waited 20 or 30 seconds and plugged it back in.
- you've rebooted your Mac too
and then tried playing problematic songs again.
New imports into Apple Music sorted by song title tends to append to the bottom of the list instead of auto-sorting into alphabetical order. So if some of the missing ones are not where they seem they should be by alphabetical logic, scroll to the bottom of the list and see if they are there. If they are, you get on your Mac, open the playlist, click title twice to resort the list and then they move into place.
If you display playlists as type playlist on that Mac, you'll need to switch "View" from "as playlist" to "as songs" then click Title column header twice to sort those at the bottom into the list where you expect them (alphabetical). After verifying they are there, you can then switch View "as playlist" back again so it displays as playlist.
HOWEVER, now that they are mixed in as expected on Mac, they will probably STILL NOT be sorted that way on AppleTV. AppleTV/tvOS seems to remember the
original sort, not any new sorts... so the new imports will probably still be at the bottom. The only remedy for AppleTV sorting that I've found is get on Mac and duplicate the playlist, delete the old copy, so that the new playlist copy (properly sorted) is now in change and sync the new playlist (copy) to AppleTV. That works every time but is unfortunate that one must jump through this many hoops to get simple alphabetical order on AppleTV as one adds new songs.
If the songs that will not play at all, still do not play but do play on iPhone, try airplaying them from iPhone to AppleTV to see if they will play at all. If so, I suspect you have 2 copies of the song and one is a format not compatible with Apple. What are the sources of the songs that won't play:
- purchased from iTunes,
- ripped from your own CDs or
- found somewhere out on the internet or unknown (maybe friends got them from who knows where and shared them with you).
If the latter, they may be in incompatible formats that iOS can handle but tvOS can't.
If they will play on Mac, perhaps you should choose those songs on Mac, File (menu), Convert, Create AAC version to convert them into a compatible format. Then try them on Mac. If they play, try them on phone and AppleTV. Successful conversions to AAC should play fine on AppleTV.