Me and a friend both bought the CDV version in Finland and are having the same prob. Running it on WinXP + all patches, I'm behind a shared connection but that shouldn't make any difference.
We started playing a tutorial that worked fine for a couple of turns. He has to host because of my connection and the connection loss seems to be in his end. This is our first CM so haven't tried playing on previous games..