On my laptop (Pentium M, 1.6 GHz, 1 GB RAM) it takes exactly 68 seconds from the time I press Enter in the GDM login screen, until the GNOME desktop is completely loaded (the last applets appear and the disk activity stops). This is GNOME 2.16.1 from Ubuntu Edgy.
This is after a fresh reboot (so, nothing in disk cache, except for what Ubuntu's readahead loads). The startup process is not interfering (I waited until the disk activity stopped before I logged in).
What does GNOME load? A large wallpaper (2304x1280 -- I use dual-head), xcompmgr, Tomboy, Network Manager applet, a bunch of GNOME applets on three panels (netspeed, gweather, battery, sound volume, two clocks, window switcher, workspace switcher, two window lists, two system managers, CPU frequency, trashcan, 7 launchers). And the usual GNOME processes (nautilus, gnome-settings-daemon, etc.).
Still, 68 seconds is too much. I ought to figure out how to hook bootchart to this thing and start filing bugs.