Денис, попробуй на роутере UPnP включить в настройках, Xbox поддерживает этот стандарт, и сама даст команду роутеру на проброс нужных портов. Ну или руками проброс порта 3074 (UDP и TCP) сделай в настройках Firewall или добавь IP консоли в DMZ (тогда для нее все порты будут открыты, но для консоли это не смертельно).
Если же проблема только при использовании VPN, то надо смотреть открыт ли на сервере 3074 порт