Side Note: This worked before upgrading from 4.7.8 to 4.7.10.
When we go to Advanced Search (ourdomain/civicrm/contact/search/advanced): Address Fields, enter a Postal Code and a range (ex: Find contacts within 25 miles), and click "Search," CiviCRM returns an error like:
No matches found for: Proximity search to a distance of 20 miles from 78660, UNITED STATES: We could not geocode the destination address.
I went to the sandbox (http://dmaster.demo.civicrm.org/civicrm/contact/search/advanced ) to check/test this, but the sandbox does not offer the option to search by proximity to a Postal Code. The sandbox is running 4.7.11