I had a similar issue when I applied for a credit card JUST AFTER MOVING. If you just moved out of the state there is likely no public record of your new address in the new state. For AMEX they just asked for some bank statements with the new info. These other companies seem to want to outright deny you