The connection problem on Xbox is fixed in the latest update, and was specific to that version (related to the Xbox ID).
Do the connection problems seem better or worse at particular times of the day/week? If so, it could be related to network congestion or throttling by your ISP(s) during peak hours.
I don't recall seeing conformation of the ports used by the Enhanced Edition (I can check tomorrow), but from a D:OS topic (so the PC version):
The game's client will try to assign a port in the range 23243-23252, the server in the range 23253-23262. While forwarding these ports on your gateway might help, there is no guarantee the gateway will assign an external port in this range when connecting to our NATPunch server (this is the port that will be assumed to be the external port for all connections).