That can happen. One of my colleagues had this problem, except he solved it by not being American (he'd not returned a form which they'd sent, asking him to confirm his lack of American citizenship).

I expect the reporting requirements are a burden for small banks, especially ones competing heavily on price rather than offering a full service. I'm not American, but am a similar burden to a bank, and was strongly advised to open an account only with the country's largest bank.