I setup my box for auto-login and it does this on every login. In my case it's nm-applet/network-manager family of apps.
btw the problem has been around for some time, evidently some half-fix got undone during a package upgrade, but i digress...one solution is here
WHATEVER is causing the problem you could add after login but before everything else: a script with libpam-gnome-keyring to unlock it...the package to get this tool is: libpam-gnome-keyring at least in 11.04
#launch useful stuff for gnome
#first unlock the default keyring...
echo YOUR_KEYRING_PASSWORD_HERE | /usr/libexec/pam-keyring-tool -u -s
#then run nm-applet in the background...
and the "bugs" on bugzilla are probably being continually given priority of low because it's only for autologin users. it doesn't happen "out of the box" only due to customization. just trying to help you understand why it seems like the devs don't care. it's not a coding problem, it's...well...something else.
proof video that it is nm-applet is here
and the reason it freezes the menu system is not because of gksudo, it's because it's an applet trying to start that grabs the tray and locks the menu-system. at least in my case you can still launch icons on the desktop. try putting a shortcut to a terminal there if you really must go mucking about with the prompt there.