One other thing, we have just put Win 7 Ultimate onto another machine (an HP dc5800 - only a year old) here in our IT department at work and it's exhibiting the same problem...it won't restart. We dont have any other programs loaded or running on this machine, not even an AV program. We did this specifically to test out the theory that Norton might be causing the problem??? Now we're really stumped!
Another point - Norton was running (along with other programs) on my HP xw4200 with Windows Home Premium and there were no issues; It restarted fine. Surely this suggests that there is a difference in the build between Home Premium and Ultimate that is causing this restart issue???