I have the same problem. I try to enter an address in the search window or through the Change Location option and it comes back with "We couldn't find any results for (
new location) near (
current location)." I can find a business by name or type near my current location just fine, but I can't get Live Search to recognize an address.
