Problem solved. I went back to my server and found a button "Connect" in the settings. After that I just had to reinstall the xbox app and it found my plex server immediately:-).
Odd that's required for the Xbox, while other devices on the same net don't need it.