I had the same problem (Xubuntu to Ubuntu, both 8.10). On both machines, XDMCP was enabled, but still no connection. Then just for fun, I decided to check if I had enabled the firewall.Nope. The firewall wasn't running. So I decided to run Firestarter. After installing with
I set a policy to enable incoming connections on port 177.
sudo apt-get install firestarter
Now XDMCP works again, although it seems a bit slower. I still cannot start a nested X-session with gdmflexiserver.returns "Cannot start new display. Perhaps the X server is not configured correctly," or something similar.
UPDATE: solved gdmflexiserver problem by installing Xnest, Apparently it is not installed by default. (sudo apt-get install xnest)