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.
When you are at the menu screen it shows PRESS A. When you do it connects to the server and sync. And only then you can load the game.
