First, a startup's advantage is that you're small. You don't have to worry about serving 100 million users. That means you can make your life a bit easier as you grow. You can use a relational database while you're small, add memcached as you grow, denormalize, etc. AppEngine makes you develop your application to your end point in some ways. You can't use the techniques that get you out the door fast with a high-quality product. Rather, you have to over-engineer your product to scale to a number of users you'll likely never have. Take Stack Overflow as an example. They're a really successful service and they're running on 5 servers and a SQL database. Now, I'm sure they've done caching and a bit of denormalization, but the key is that they could launch without doing that and as they got more and more users they could add that in.
Second, Google's infrastructure doesn't really have capabilities for some of the cool things. For example, geolocation is a pain (http://code.google.com/appengine/articles/geosearch.html). MapReduce doesn't really exist. I mean, there are ways to deal with your data. The key to MapReduce is its distributed nature - that portions of the data can be computed on different boxes at the same time and then returned. This limits your ability to do the kind of warehouse data processing that can give you really cool results. And AppEngine is meant for web apps, not things trying to compute stuff like Google does. Google is addressing lots of things. You can now get incoming email. They introduced the task queue. But you're beholden to a third party for a lot of things. Part of being a startup is trying to be beholden to yourself and changing course quickly as you see something important. AppEngine might limit you there depending on what you're looking to do. Of course, it might also help.
Third, you're locked into Google's cost structure. It isn't expensive or unfair. However, it is likely to be more expensive than owning your own boxes if you're large and you have the issue that Google may not lower prices in step with competitors. Amazon has been aggressively cutting prices, Linode has been upping RAM, etc. It's a lot harder to migrate away from App Engine.
Fourth, you're beholden to Google for your application's health. Google is a great company with wonderful engineers and AppEngine isn't abandoned at all. That said, they have had datastore problems that saw the time to get one entry from the datastore rise to 1.5 seconds or higher. Even after fixing the problem, it isn't the fastest option out there. Note, App Engine is made to be scalable and Fast Enough. It isn't tuned for pure speed. Basically, you have to start closer to the more difficult to build, highly-scalable architecture that you could be building as your site grows.
It's a cool product. The problem from my perspective is that there's little reason for me to engineer a site that scales to high levels if no one is going to use it. I don't know how many people will use a site until it's built. I have a better chance of people using my site if I can a) get it out quickly and b) add the features users want rather than the features that are easy with AppEngine. I'm not going to get all my users overnight. In the months it takes to get lots of users, I can optimize my code. Plus, if it takes off, I think it would be a bit weird to be beholden to a single vendor. Yes, there are open-source App Engine mostly compatible things out there and work arounds. Still, it's easier to move from Linode to Amazon or Slicehost to a physical server.
I've rambled a little too much, but it's half past midnight.