I have the exact same problem on Mac OS 10.5.8. It only started happening recently and I looked at my update logs. It seems to have started after I did software updated on 4/6/10, namely Quicktime 7.6.6, ProKit 5.1 and Pro Applications Update 2010-01 (1.0).
I think these updates are what killed Final Cut Pro.
Also, fresh install? Seriously?! That’s not a solution. That’s a lot of time and a lot of effort for something Apple obviously broke in an update. You should never have to do a “Fresh Install” of the OS on a production system to fix an issue with a single set of applications.