Not sure if this will help, but might be worth a try. Something that I've noticed at least with my 8310, before using a gps app, 8 out of 10 times, I need to Options -> Advanced Options -> GPS then on that menu, do a Refresh GPS, then go back to the GPS app and it's worked. I've had to do this Superpages mobile, MS Live Search and Travel Channel Go often. Don't know why, but that's been the case with me.
hmm..so you don't have a data plan with you phone? That might have something to do with it. Or has this worked for you before, or just in a different location?