Toraricky: Okay, I looked a bit into this. I think it's a Firewall issue. Strange, because it didn't give me any problems yesterday; on the other hand, we had another update today.
I solved the "game connection error" by adding Alien Vs Predator Classic 2000, GalaxyClient and Galaxy Updater to the list of exceptions in the Windows Firewall Settings. While Alien Vs Predator Classic 2000 should be in the list after clicking on "Add Program", both of GalaxyClient and GalaxyUpdater must be selected from clicking "Browse", going to "C:\Program Files\GalaxyClient" and selecting GalaxyClient.exe and GalaxyUpdater.exe.
This is quite strange, since when Windows Firewall blocks a program, it notifies you of it, so you can unblock it easily without messing with the Firewall exception.
Let me know if this solves the issue for you.
I've got the same problem, I've done what you've suggested but no luck so far. I even tried disabling my anti-virus completely, but still "game connection error"