One more thing: There is a reported but unfixded bug in kdm in
Debian/Ubuntu going back a long way which is causing some xdmcp
configurations to fail when they really are ok. If you look in your logs
you'll see reports of kdm_greet getting memory corruption if you are
getting this problem. As a result of this problem I recently migrated a
bunch of thin client servers to use gdm instead of kdm.
You didn't specify which log but I didn't find any such errors in either
kdm.log or Xorg.0.log, nor did I find any other related errors in the log.
Maybe I'll try switching to xdm just to see.