Thanks for the suggestion Disillusion but I think i've already done this, the xorg.conf file was blank so I replaced it with the content of the xorg.conf.1 file which I assumed was a backup. I also checked the settings in the file afterwards and everything seemed ok.
I've also checked the settings in the Xaccess file and ensured that anyone can get a screen.
The problem changed when I changed from gdm to kdm, the error now says something like Manager rejected request or something to that effect. I'm sure its something to do with the settings on the gutsy machine so i'm looking though those.
One thing though, before I switched to kdm there was a login management tool on the menu which is now gone, I assume that was the gui for all these settings files, Is there some way I can get that back?
btw there is an official bug logged with xdmcp in gutsy
Here but I believe it affects only gdm and concerns dialing out of the gutsy machine rather than dialing in (there is a workaround apparently for dialing in, but that didn't seem to work for me).