This is true. I have a friend that is American and married to a Swiss man. They wanted to return to America but he was denied because of a conviction he had when he was 23. He pleaded no contest... (He is 45 now.)
He can simply file for a waiver of excludability. This is especially true if he married a US citizen. It generally takes eight months to process.
The form can be found under forms at http://www.uscis.gov under forms.