Note: I will primarily discuss access for blind users here, since that is what I am most familiar with. However, some of this applies to other disabilities as well.
In the Beginning
In the beginning, there was no accessibility whatsoever in Android. It would have made sense to design it from the start with accessibility in mind, which would have made it much easier, but as is sadly so often the case, this wasn't done. Nevertheless, many other platforms have managed to recover from this oversight, some with great success.
Then came the Eyes-Free Project, which created a suite of self-voicing applications to enable blind users to use many functions of the phone. Requiring blind users to use these special applications limits the functionality they can access and completely isolates them from the experience of other users. This is just a small step away from a device designed only for blind users. I guess this is better than nothing, but in the long-term, this is unacceptable.
Integrated Accessibility API and Services
With the release of Android 1.6 came an accessibility API integrated into the core of Android, as well as a screen reader (Talkback) and other accessibility services. A developer outside Google also began working on a screen reader called Spiel. This meant that blind users could now access standard Android applications just like everyone else.
Unfortunately, the Android accessibility API is severely limited. All it can do is send events when something notable happens in the user interface. An accessibility service such as a screen reader can query these events for specific information (such as the text of an object which has been activated), but no other interaction or queries are possible. This means it isn't possible to retrieve information about other objects on the screen unless they are activated, which makes screen review impossible among other things. Even the now very dated Microsoft Active Accessibility (the core accessibility API used in Windows), with its many limitations and flaws, allows you to explore, query and interact with objects.
Inability to Globally Intercept Input
In addition, it is not possible for an accessibility service to globally intercept presses on the keyboard or touch screen. Not only does this mean that an accessibility service cannot provide keyboard/touch screen commands for screen review, silencing speech, changing settings, etc., but it also makes touch screen accessibility for blind users impossible. A blind user needs to be able to explore the touch screen without unintentionally activating controls, which can't be done unless the screen reader can provide special handling of the touch screen.
Inaccessible Web Rendering Engine
The web rendering engine used in Android is inaccessible. In fact, it's probably impossible to make it accessible at present due to Android's severely limited accessibility framework, as a user needs to be able to explore all objects on a web page. This means that the in-built web browser, email client and most other applications that display web content are inaccessible. This is totally unacceptable for a modern smart phone.
IDEAL Apps4Android's Accessible Email Client and Web Browser
IDEAL Apps4Android released both an accessible email client and web browser. The accessibility enhancements to the K9 email client (on which their application is based) have since been incorporated into K9 itself, which is fantastic. However, access to the web still requires a separate "accessible" web browser. While other developers can also integrate this web accessibility support into their applications, it is essentially a set of self-voicing scripts which need to be embedded in the application. This is rather inelegant and is very much "bolt-on accessibility" instead of accessibility being integrated into the web rendering engine itself. This isn't to criticise IDEAL: they did the best they could given the limitations of the Android accessibility API and should be commended. Nevertheless, it is an unsatisfactory situation.
More "Accessible" Apps
There are quite a few other applications aside from those mentioned above that have been designed specifically as "accessible" applications, again isolating disabled users from the normal applications used by everyone else. Again, this isolating redundancy is largely due to Android's severely limited accessibility framework.
Unfortunately, even though Android is open source, solving this problem is rather difficult for people outside the core Android development team because it will require changes to the core of Android. The current accessibility framework needs to be significantly enhanced or perhaps even redesigned, and core applications need to take advantage of this improved framework.
While significant headway has been made concerning accessibility in Android 1.6 and beyond, the situation is far from satisfactory. Android is usable by blind users now, but it is certainly not optimal or straightforward. In addition, the implementation is poorly designed and inelegant. This situation is only going to get messier until this problem is solved.
I find it extremely frustrating that Android accessibility is in such a poor state. It seems that Google learnt nothing from the accessibility lessons of the past. This mess could have been avoided if the accessibility framework had been carefully designed, rather than the half-done job we have now. Good, thorough design is one of the reasons that iPhone accessibility is so brilliant and "just works".