Android :: Strategies For Large Volume Of Location Geocoding

I have an application that uses the Google Maps API to geocode distances between lat/long pairs as a way of displaying people near to you on your phone (currently Android, working on iPhone). The issue is that even with a test group of 40 users, we are taking upwards of 10 seconds to do our calculations and send the results back to the users. While 10 seconds sounds like a long time, it's not really an issue as far as the client app goes because it's not a real-time update of people's locations (the updates occur every few minutes). Obviously this is a problem though since we'd obviously love to ramp up to tens or even hundreds of thousands of users. I'm curious if anyone else has any experience in this arena in regards to using the Google Maps API for calculating distances between points for large volumes of data?

As an aside, we're using Rails on the server, which is where all of the location calculations are occurring. The phone(s) are merely displaying the maps and updating the server with lat/long coordinates.