Since Google Maps Mobile isn't working with GPS. At least for me. I am trying Beyond 411. I'm sort of having the same problem. I just want it to search via GPS for stuff near where I am. It's proving to be quite difficult. In Beyond 411 it wants to search from your default previously setup locations of Work or Home. Even though it says GPS availabe in Beyond 411. How are you guys searching for locations near you?

On the start page, navigate to the upper right corner, where it says "Work". Click on your trackball and select GPS. Now it will search for things in the vicinity of your phone. I'm not sure why this isn't the default since most of us already know what is near home and work.