Where do you try to register your domain? I.e. who is the registrar? Is it Oracle/Dyn? And what domain name are you trying to register?
Also, can you post a related screen shot where this message appears? We other users need this information, else we are not able to suggest next steps.
Per ICANN regulations, all domains must have a verifiable physical mailing address. If you have not already, (and assuming it was registered via Dyn originally) you will want to verify on your account that the listed information is accurate. You can do so via the following:
-sign in via http://account.dyn.com
-click on my services
-click on domain registration
-click on edit on the contact
-or add a new profile and apply it to your registrant, billing, admin, and tech.
If you can't edit the contacts there:
-click on my account
-click on contact manager
-update your information and delete any unused entries.
If you are still having difficulties, you will need to contact support via "contact support" under "My Services" after logging into your account and they will assist you in verifying the address.