I have had issues with LMDE taking 5-6 mins to shutdown it just seemed to stop as if waiting for something to happen, it would eventually shutdown. Also happened on reboot.
Yesterday I had to add an item into the Startup Applications Preferences of System Settings (why are there two of these?) and while I was there I checked to see if there was anything that didn't need to be run and found two programs that weren't even installed anymore, so I removed them. When I then rebooted the PC the delay had disappeared.
Really don't understand why this should be.