I figured out the solution...well it worked for me at least!
You need the startup-notification package, which is part of gnome and can be found here:
http://ftp.gnome.org/pub/GNOME/deskt...on-0.8.tar.bz2 ...the nautilus-program-choosing.c file doesn't visibly link to it that I could see, but there is a comment below the timestamp function that mentions startup notification. Get that package, compile it and see if that fixes the problem.
The gnome developers should really have a check in the nautilus configure script to see if that library is installed.