Request the reason they denied you or at the least get a copy of your own arrest/criminal history from every county you've ever lived. Could be something on there that you're not aware of, something erroneous.
Someone I know was once questioned during a criminal investigation. He was NOT arrested, NOT booked, NOT charged, he was asked to come to the police station for questioning and he did. The disposition of the complaint was that there was insufficient evidence to substantiate that a crime occurred = no charges. But due to an error in the reports filed by the investigating officer, it went on his record as being arrested and detained. So when he was responding "NO" on the security clearance and job applications if he had ever been arrested, they concluded that was a dishonest answer.
He had been to several job interviews and passed over with no explanation in spite of being very qualified. The only way he discovered it was that one interviewer specifically asked him about this discrepancy. It had happened like 16 years prior.