I have noticed this same issue, both in 7.04 and 8.10. The "first time" after
a boot that I activate the the "shutdown" panel, it takes at least 2 to 3
minutes to initiate. I'm usually doing this for a screen lock rather than a
shut down.

Now after this first time - the panel activates within a second or two after
selection. Acts normally until the next restart, then back to several minutes
for the next "first time". I suspect there is an underlying service which
controls the shutdown/logoff/screen lock panel which is not starting at boot,
and is only called and loaded when it's asked for. The issue is a bit
irritating, but not to the point I've gone digging to fix it.

Mine (8.10 64 bit and 9.04 64-bit) shuts down right away. I wonder what
programmes you might be running in the background that might do this. Do you
shut down any running programmes first?

Check your system monitor (Administration) and sessions (Preferences) to see
what processes are running at shutdown. Try shutting them off manually one at a
time to see if one is making a big difference.