I got the same type of error in CS5; and, it’s just as you wrote…I found a very tiny space at the beginning of the time line. Sliding the footage over resolved the problem. Perhaps Adobe should add a check for blank space option in their check project tool?
Thank you for doing the homework on this one. It saved me considerable time and is much appreciated.