FWIW, You mentioned in the OP that you added billing information, but unless their account is very very old: billing information is required on sign up, afaik.

It's possible they did something goofy with a card that expired or a prepaid card upon opening the account that's causing the current issues.