As far as i'm aware, its the Games for Windows Live client is not starting up when the game is launching. I had this same issue and did the following which worked for me.
Shut down any MSN powered application
Download the latest Game For Windows Live client from here
Once it is installed, restart your computer.
Then try launching the game.