I have a "new" HP Envy and the startup is fine but the shutdown takes about 4 minutes. Have run also run ccleaner and superantispyware and the shutdown was fine for one time but then went back to the 4 minute shutdown. Also tried reinstalling a couple of the programs to see if that helped. Nothing.
HP Envy Touchsmart. Same symptoms. May be network related, because I did get a fast shutdown once, when there was no network attached in that particular session.... Will test and report.