Where does it freeze up? Where it says "saving your settings" or "windows is shutting down" ?
If you leave it does it eventually shut down? (Or put another way, what's the longest you've waited?)
It implies to me that an application is still "hanging on" to some aspect of the system; that needs exploring, really, though a reg cleaner might do the job.
An application like Process explorer, Asquared hijack free etc can inform as to what is being used at any one time.
Next time you go to shut down, open task manager and see if anything is using significant cpu.