I can't seem to launch a co-op quest. I form a party and launch the co-op quest, but after a few seconds it doesn't load and gives an error "Launching game host failed . Then it says "Games for Windows - LIVE Connection Failed: (User1) could not connect to (User2)." User1 and User2 are the actual user names.
Another time I tried running it with someone else and I got an error that the games were out of sync and my AOEO client crashed.
Okay, try uninstalling and reinstalling the game. Also check the Age of Empires: Online throuble shooting FAQ here: http://forums.xbox.com/gfw/games_discussion/pc_games_a-d/f/292/t/57049.aspx.
Make sure that you are in one of the Live Supported Countries as, if you are not in a supported country, that may be the casue.
If you try all of those things and it's still giving you those messages check this post: http://forums.xbox.com/gfw/technical_support/connection_networking/f/265/t/20431.aspx
for some network and connection related troubleshooting.
I have the same problem, and none of your solutions were helpful.
Check this thread out, seems to be a known issue with AoE:O.
Are you using the Steam version of the game?