You have to specify if it's a Address or a Place (if your initial search doesn't work, which is pretty much always)
It used to be the case that you could search for the name of a store chain (e.g. Systembolaget - the state alcohol stores) and it would show some of their stores on a map around you, nowadays it picks some random one (never close to where you are) and displays that instead.
The same thing has started happening for lots of places that it used to find before, that are now seemingly just gone. In the meantime Apple Maps has been consistently improving and is now my go-to maps application on the phone.
But the "new GMaps quirks" are awful
... in Queens. http://random.fennecfoxen.org/screenshots/gct.png
Hemnet recently created an OSM layer just to get building outlines again.
We got to a proof-of-concept stage but it's currently on hold (the other two cofounders quit/don't have time for it either), but I think it's certainly a need that isn't being serviced by Google.
My project is called EncontraloCerca, it's supposed to be for Uruguay and Argentina first, but when we get to Stockholm I'll let you know :) .
I thought I was the only one. I've found Nokia's HERE Maps to be better overall than Google Maps when I just want to find a place to eat or shop or visit. For navigation, they are about equal in my experience, i.e. if you absolutely know your destination address, Google Maps is as good as, or better than, Nokia's maps at getting you there.
In case some of those terms are undefined: A spot just off the coast of Nigeria is where the 0 degree longitude (Prime Meridian) and the 0 degree latitude (Equator) lines meet. If Google Maps goes there, something zeroed out its latitude and longitude variables, something you'd think they'd test for every so often.
https://www.google.com/maps/search/Systembolaget/@59.326755,...
Having just gone through a recent home buying exercise in mid-west I always reverted to bing maps for a "birds eye view" as they had 4 directions of shots from their plane camera while google just had satellite then went into some kind of rendered/extruded view which was kinda eh.
Now if I compare that to our office in SF then google better than bing for zooming in.