Apologies if this seems inappropriate but I've found enough people who have had the same problem, even though it's not directly a fault of the developers.
Zero Day Protection has a bug that affects some (presumably a minority) Window 7 64-bit users. The program claims not to be able to connect to the LIVE service, I have wireshark logs that prove that it connected (via a simple https connection) to one of the servers that zdp.gamesforwindows.com points to - handshakes correctly and exchanges data.
The GFWL support people while very helpful (apart from the one that claimed the game isn't released till yesterday) didn't really know that ZDP existed and didn't seem to have many troubleshooting documents (even with prompting on what to search for). I'm now stuck in an 'upto' 15 days "elevated support" queue - assuming I'm somewhere near my computer when they call...
Considering the fact that I could have probably downloaded the game and cracked it less time than I spent on the phone with Microsoft, I'm still at a loss as to how publishers think this helps them as it certainly doesn't seem to hinder the people who pirate it.
If anyone has suggestions for how to fix this, please post, I'll update this post if and when GFWL get back to me.
I got that message all yesterday and somehow when I tried this morning after trying it all night (10 hours) finally passed the check and was able to get into my game. But quite an annoying system, just keep trying and hoping for the best.
and like that, it works again. obviously server issues...