GAE has problems, but I think the root is just how unique everything is. That manifests itself in people using a datastore that they don't understand, with Google expecting them to know how many writes an action will take and whether that feels like the right number of writes or two orders of magnitude more than if they made a different decision about how to store their data and solve their problems.
It also manifests itself in the lockin that Heroku mostly avoids (which is a huge problem if some subset of users get to a point where they realize "whoops, this would be much easier if I could do things Google won't let me do, time to leave").
I think a good counterexample is Engine Yard and GitHub. Engine Yard had a somewhat limited offering (especially for what GitHub was willing to pay) that didn't really fit with GitHub's heavy direct disk I/O. (Most Rails apps almost entirely read and write from the db, but GitHub does a lot of direct operations on the git repositories.) But GitHub was still just a Rails app, not an app for some specially-designed Engine Yard framework. So it was fairly painless for them to decide to solve the problem in a way that didn't fit with what Engine Yard would offer them and migrate to their own hardware. It wasn't easy, especially since they weren't solving an easy problem, but at least they didn't have to replace their database.