Same problem here.
Two machines...early 2008 Mac Pro, and a MacBook Pro 15. MacBook updates saw no problems, and start-up/shut-down are speedy. The problem is with the Mac Pro.
Upgrades were done per the recommended method; no clean installs, just upgrades. Now, with 10.6.2, there's no improvement. About 30 second start-up on the Mac Pro. Everything runs fine, and fast. It's just that I've lost the start-up speed (which is darn near instant on my MacBook Pro.)