Success ....... Many Results Found !
I did the same thing as joejoem and it also seemed to fix the 'no results found' problem.
I ERASED ALL BOOKMARKS, both Bookmarks and Current from my 5s.
Now its flashing results quickly and finding multiple choices in beautiful bursts.
I've had at east 3 versions of iphone, , been traveling for work for 8 years, and I'm sure many of these Bookmarks have been migrating forward thru iOS versions, and I remember them importing when I did the big iOS [6?] upgrade that switched from Google Maps to Apple Maps. Yes that's when this problem started.