Some have reported greater success (for U S A addresses) when they used the U S Postal Service (www.usps.com) site to validate their address and then used the resulting address and added it to the aa.com record idem.

Some systems can not accept characters they have not been programmed for - e.g. "#". And as dcAA says, AA's validation tool may not be up to date.

Presumably, an agent would be able to enter the address as needed / override the system.

Of course, I'd not call during hurricane Sandy disruptions to correct my address.