You need to make sure your allowing the game launcher through both private networks and public [in the case of windows firewall] - it should have set that up as part of the install - unless your using a 3rd party firewall?
I would contact Support, using the link in my signature, or phone them on the number in the Manual- and tell them the software your using and they should be able to advise you further.
You need to make sure the Ubisoft Game Launcher also has rights.
Are you using an ATI graphics card? - seems a few people with those cards are also having issues - if your using ATI it's VERY important that you contact support - so they can see if there's a trend to the problem, eg, certain driver / or cards with the problem - so that AMD can update the driver asap
Using the weblink is free, but if you want a faster service, and don't mind paying for the call - I suggest calling them and speaking to a person to check whats wrong.
Sounds like it can't talk to the servers - that's sounding like an launcher issue, if it can't verify the CD Key or see the OSP servers - so double check the launcher is able to get through the firewall..
Or you can try a re-install of the game, make sure if you can, to select the 'configure widows firewall' option when you configure the install options [it's on the other titles, so I assume it is on SC:C]
That should set up windows firewall for you - allowing everything it needs through
The above is just information, from other titles - most issues connecting are down to the PC's firewall.
These forums are not a replacement for support, and I do not work for them, so my knowledge is limited - so you need to start a support ticket with them, they ask you for a full system dxiag when you submit it.