Cannot cast media from Plexamp, Plex Desktop (Linux), or app.plex.tv in Chrome to Plex on AppleTV

While playing music, or watching movies or TV shows, I cannot cast my media to my AppleTV. It does not matter if I am playing a one off item, or part of a playlist, or just to connect before I play anything. The AppleTV does not show up as a player I can target despite the fact that I enabled the Advertise as a player setting in Plex for AppleTV.

I have tried casting from Plexamp on my Android phone, the Plex desktop app on Ubuntu, or app.plex.tv in Chrome.

I am using the latest player and server version so I cannot say what the problem is.