I was having the "invalid address" issue as well with my wife's iPad. I verified that our address was valid, our credit card issuer's address matched our home address and that our address was recognized by the USPS. Still no luck. I tried different credit cards (with matching addresses) and still got the same error.
So then I tried these steps and got her iPad downloading apps again (YMMV):
1. When the "Invalid Address" popup shows, change your billing type to "None" (as if you were going to use a gift card.)
2. Enter Apple's address for your billing address and zip code:
1 INFINITE LOOP
CUPERTINO CA 95014
3. Save your "new" address.
4. Download a free app from the App Store that you don't already have (in this case the iPad was trying to download the iBooks app.)
5. After the free app downloads, try to download your paid app. The iPad prompted me for payment information.
6. Enter the correct card and address information.
If all goes well, the App Store should charge your card and you should have your new paid app.