Have you tried holding down the power button for an extended period of time? When my machine gets out of line this 'hard' shutdown seems to do the trick. Not pretty, but works.
Why are you shutting down your machine? My laptop has been on for about 17.99 months out of the last 18. Sleep is fine. The only time I restart is for installs.