i suspect that auto-complete relies on the SQL LIKE statement which does not exist on GAE. in general GAE is not setup for queries that return lots of results (which is what a LIKE query tends to do) and so these are pretty hard to do there.
yup, web2py has done a great job of database abstraction, but the NOSQL DB's are a little less well supported. maybe try the SQL option on GAE (still private beta, but you can request an invite)
