Reasons for not qualifying include bankruptcies, foreclosures, and judgements. As of October 2011, they also look at charge-offs and collection accounts. Your parents may have a poor credit score due to late-pays, but if they don't have these other things, they may still qualify. if they have charge-offs or collections that they went back and eventually paid, you have the opportunity to appeal a denial and provide proof of payment.
It hurts nothing to go ahead and try to get the PLUS, because you can't get the extra student loan ($4,000 first year) without that denial.