I've had this problem with my old iMac G4 from OS X 10.1 until OS X 10.4, sometimes I reinstalled OS X, the problem went away only to come back, sometimes the problem stopped without me doing anything. It went from 4-5 minutes to 30-40 seconds. Strange, back then (like in 2002 or 2003) I called Apple and no one could give me an answer.
I have never encoutered this problem on my intel iMac though.
Sorry I don't have a good advice... but you can do the usual, repair permissions, verify disk, did your mac come with a hardware test (DVD)? Is this the only problem you have?
