Have you SpeedTools installed maybe?, those utils install some weird items that prevents the normal shutdown be done. If you have SpeedTools installed look for these items inside the StartupItems folder
"QuickBackStartupItem" <-- guilty
"SpeedToolsDTStartupItem" <-- guilty
Look for the StartupItems folder inside the Library folder of your hard disk, not your User Library folder. Delete those two items, not the folder.