I would try and run the 'Disk First Aid' Application from the OS X Boot CD first. 'Repair' the disk, and 'verify' any permissions errors.... See if this helps.
If you still have no joy, try the following:
FSCK. (self-diagnostic/repair utility built into OSX)
This runs only on the boot up drive, and is only accessible when you start up your computer with COMMAND-S held down.
Wait for the computer to run through its startup, eventually you'll arrive at a prompt.
Type in "fsck -y" and watch as your Mac checks itself out. If you've never run it, it will probably find some things in need of tweaking. Run the program over again if it has modified your disc. Stop running it when it tells you your disc is OK.
You can then type in "reboot", to restart your machine normally... See if it helped...
Only reinstall as a total last resort....
If you do have to reinstall OS X, when you go to the 'install' page, if you choose the 'custom' option, you get an option to preserve all your accounts and data... Pick this option. All your data should be preserved... However it is not 100% guaranteed.
I would only reinstall after all else has failed.
Peace,
Marc
P.S. What actually happens when you restart the Mac? Does it even get to the OS X Boot up screen? If so what stage does it stop at etc... If you could post these details it may be easier to give you some advice...
P.P.S. I learned the lesson of installing the brand new updates to my cost. If you are running 'Mission Critical' work... WAIT! Don't install anything until you have finshed, and have time to tinker with the machine should anything go wrong... Ideally wait for a few weeks after the update to see if anyone else has major dramas on similar machines to your own...!
(Cheers to awcopus... I nicked the FSCK details from a post of yours last week. You explained it much better than I could...!)