The main Android programming language is Java, and the Android OS comes with a whole collection of standard Java libraries, from the JRE and elsewhere. It's also straightforward to include other Java libraries in your Android application.
However, you'll get a problem if a future version of Android ever includes a version of the library that's embedded in your application – the Android classloader will always pull in the standard OS version of the library rather than your own.
What's more, the OS can bundle "silent" copies of libraries, that don't appear as part of the advertized APIs. So there's not documentation that (say) Android 2.3 adds
javax.sipto the system, or that Android 3.0 adds
com.google.i18n.phonenumbersinto the system namespace, at a higher priority than anything embedded in your app.
This means that your app can be working fine, and then fail miserably on the next version of Android for hard-to-debug reasons, because the OS now includes the library that your code depends on – but of a completely different version. All of a sudden, an
.apkthat works fine on Android version X fails with
NoSuchMethodErroron Android version X+1. (Here's an example of exactly this problem.)
This just seems like a straightforward bug in the Dalvik classloader to me, and as yet I've not found a good way round it. Others have suggested tools like JarJar to embed the library code more indivisibly, but I've not tried this yet. But of course doing that require prescience: spotting in advance which Java library files might possibly get incorporated into Android in the future. So maybe the safest advice is to embed/rename any Java libraries that you pull in to your application.
[Update 2011-09-03: I've put source code for an Android app on GitHub that allows you to look at what libraries are available on the system, using Java reflection functionality. So at least it's easier to figure out when this problem is occurring.]