Description of problem:

type=AVC msg=audit(1196509401.288:20): avc:  denied  { search } for  pid=2806
comm="dbus-daemon" name="gdm" dev=dm-0 ino=3211273
scontext=system_u:system_r:xdm_dbusd_t:s0-s0:c0.c1023
tcontext=system_u:object_r:xdm_var_lib_t:s0 tclass=dir

Which would indicate SELinux needs this rule.

allow xdm_dbusd_t xdm_var_lib_t:dir search;

Which means the dbus-daemon being execed from gdm is search through /var/lib/gdm
 for something.  I am guessing this is a open file that gdm is using.  gdm seems
to work fine without this access.

rpm -q selinux-policy gdm
selinux-policy-3.2.1-1.fc9
gdm-2.21.2-0.2007.11.20.2.fc9