GAE does have some performance surprises even during normal performance periods, so it's good that you're using Memcache etc now.

Couple other ideas:

Try to minimize read effort as much as possible, so e.g. pre-calculate as much as you can and rather optimize for performance than data cost. Data is cheap, so de-normalise where you need speed. Calc offline, so add a task to calculate something and return immediately to the user.