For me this has been happening for a long time. It got to the point that even before i open the app on the xbox, i gotta grab my phone and open the app there first. As soon as the plex cloud server shows up in the phone app, i go to the xbox and open plex there. The only way it works for me! Sadly, even this workaround is giving me issues lately, ive been able to make it work by refreshing a few times with the phone app until it shows up, or i use the phone web browser to open plex there.
Hope this helps someone. I still can have a good experience with the app, I am still waiting to see if they can get the tizen Samsung app fixed for Plex Cloud. Since last year i cant use it there.
