Did you do anything else? For instance, erasing the free space in Disk Utility will cause a slowdown in boot times. Downloading the TRIM Enabler discussed in the Mac Pro forum can help if you did that.
Occasionally, an update will also cause the next reboot to take a while, but it usually fixes itself.
The more we know, the more we may be able to help you figure out what is going on.