I've had success using the geomodel open-source project for storing and querying lat/lon data in the App Engine datastore. It uses a geohash to enable querying on a single property, it's available for both Python and Java and since it's open source you can modify the code to fit your particular case if need be.
It's also worth noting that it was announced at Google I/O a couple weeks back that the datastore would someday (hopefully soon) provide native support for geospatial and date queries, using a Hilbert curve internally. This would allow fast querying for bounding box or even in arbitrary polygon queries. You can watch the video of that talk online for more detail, it's a pretty interesting discussion.