Solution: both of you press the XBOX BUTTON, then on the tile the game is running press the MENU button on xbox controller and select QUIT. Now both of you reopen the game and let it boot completely. Press A to connect to the servers when asked. Now try playing online coop.
I have never been asked to connect to any server in this nor have I ever received a confirmation of having been connected to one. So this "solution" seems a bit strange to me. In any case it didn't work either.
