This is undoubtedly an upstream issue, but ...
I've been messing about with that hp pavilion trying to get wireless working. If I boot with the eth0 NIC plugged in, everything is blazingly fast -- GDM comes up in a few seconds, the Gnome startup splash screen barely has time to appear before it's gone again, shells pop up the instant I click Open Terminal.
If I unplug the network and reboot, it all goes to hell. It takes several minutes for GDM to start, the splash screen sometimes lingers up to 10 minutes after the window manager is running, terminal windows take varying lengths of time from 2-15 minutes to open. It even takes 5-6 minutes to mount filesystems from the USB drive.
Nothing unusual appears in "top"; gnome-system-monitor is one of the apps that takes forever to launch (to the point that I thought it had crashed), but it doesn't show anything odd either. No activity in the various /var/log files. Any ideas what could be causing this?