I do not know why this is happening. Generally shut down should work properly.
Just a guess. R u guys using 3 DEs
e.g. If you have Mint 12 LISA with Gnome + cinnamon and then you install KDE.
You wont find a shut down button in KDE, as KDE is not default DE.
So you will need to log out and then login to default desktop, where you will find a shut down option. Shut down should work
Generally, I use synapse (a keyboard launcher similar to Gnome-do) and type Shut down and hit enter. Rarely use menu to shut down
Incase you have 2 De, then you will have to change the login manager
In my case I had to change from GDM to KDM to get shut down menu. Then I could get shut down in both DEs