I've had the exact same issue for over a year on multiple revs of Parallels -- both on a 2007 MacBook and an (early) 2008 MacBook Pro. Here's the best info I can provide:
-- Happens on both Tiger and Leopard
-- Parallels will hang the system while Parallels is starting up and BEFORE you can select a VM to launch
-- I generally see this behavior when I suspend a VM, shut down Parallels, and then try to relaunch Parallels -- although it's not always the 2nd time I launch Parallels after a Mac OS X reboot. It will often only happen the 3rd or 4th time I launch Parallels. Usually, there is a Mac OS X suspend or two (or ten) in between.
-- Rebooting Mac OS X will allow me to launch Parallels, as Parallels generally works the first time I launch it after rebooting.
-- I usually use my MacBooks in the closed position, hooked up to an external monitor, keyboard, and mouse -- but often 'undock' them and then use the internal keyboard and monitor. I'll often transition between both states without rebooting Mac OS X.
Based on the length of this thread, it seems time to try VMWare -- as it doesn't seem like Parallels knows how to reproduce it or fix it... Too bad. Other than this problem, it's been a good product.