I have a Nextel i710 (nearly the same phone, just without external display, flashing ringer-circle thingy, and a different color) and I have to say that the GPS is terrible. From my experiences just playing around with it (and not actaully trying to get anything accomplished), it takes forever to get a lock and even then is grossly inaccurate. I would provide actual numbers, but I just sat on my front porch (where I have taken many a GPSr reading, and got impatient after my i710 have been "Scanning for Satellites" for more than 5 minutes.
eBay is also a good place to look for a GPS that is a step up from the entry level GPSr's, but still inexpensive. I got my Garmin eTrex Vista in a "GPS Starter Kit" that included MetroGuide and US Topographical Maps for less than the price of a Vista w/ just MetroGuide from Garmin. Of course, YMMV. For all you know, you could get an even better deal than I did.
One feature that I have found incredibly useful is having a built-in compass. That way, even if the GPS thinks you are going in a slightly different direction than you actually are, the navigation arrow is pointing much closer to where the cache actually is.
Then again, nothing beats a plain old Silva Compass, and taking a bearing 100 feet out.
Kyle