There is a lot of talk going on in technical blogosphere regarding App Engine's elevating datastore latency lately. Google has acknowledged the issue and respondend here and promised a fix within a couple of weeks.
The explanation given by App Engine's team above is that this is the result of rapid growth rate of App Engines usage during past few months and I do believe this explanation.
The problem is that it also happened while Google announce App engine for Google Appls. My point of view is that App Engine should hold from expanding to new areas till all technical problems, outstanding issues and features promised in the road map get materialized. But then again who am I to tell Google what to do ?.
By the way an interesting but rather naive view has been written in App Engines mail-group about DataStore Latency affecting SEO.
One of the contributors there seems to believe that "But it could also happen nothing too because google detects that your site runs on their service" i.e. Google search could possibly will not penalize for been slow applications running on App Engine since these are running on Google's infrastructure.
Well I can tell you this can't happen since it defies search's main purpose to "provide best results for the user" besides I do not believe search results and serps can change that much within couple of weeks time (caffeine is just designed to target this delay).