Exactly the same issue for me and my boy. We're sitting next to each other. We played MP without issue in 0.2, never tested 0.3 and now in 0.4 we're having issues.
I can host, my son can't join, says the game is no longer available. I see him as offline.
He can't host, timeout at "Creating Lobby..." with "There was an issue hosting a multiplayer game. Check connection" etc
If we look at Settings/Gaming/Xbox Network, the NAT-type says "Teredo is unable to qualify".
If we try "Fix it", it'll stay fixed until the next time he tries to host a game, where it will break again
All of this points to routing issues. Any suggestions how to fix this?