We had that problem with a bunch of systems near the beginning of the year. We did not find a resolution.
It was worse with Knoppix 3, slightly better with 5.0, and somewhat better with 5.1.1
Strange thing is - 4 months later, the "same" systems worked fine - new computers with the same model number and specs.
Our theory is that a newer BIOS fixed the problem. We haven't seen it in systems newer than about June 2007.

There were some of these systems that would not boot any Live CD at the time. They all had SATA CDROM's.
We never found a solution, but most would boot from a USB CDROM, and that was sufficient work-around for them.