I cannot play music in the status "uploaded" in iTunes through iCloud (via Apple TV, iPhone, iPad)
I had this problem recently - I could see the songs in my library on my iPhone, but I couldn't play them. In iTunes, the iCloud status of the files was Uploaded.

What fixed it for me was plugging my iPhone into the computer with my iTunes library, and syncing. It didn't seem to transfer any files (other than doing a backup), but after that, I could play all of my songs on my phone.

This might help for your iPad and iPhone, but unfortunately, probably not the Apple TV.