Hmm, if you do a disk cleanup then try defragmenting the hard disk then post back the results... Also can you take a look in the task manager processes tab (CTRL+ALT+DEL) and see how many programs are running..
It could be that its taking so long because there are a lot of things it needs to close :?