Just to let the subscribers of this thread know:
Based on bitcoinj, I've created and uploaded a first, experimental Bitcoin wallet implementation for Android:
http://market.android.com/details?id=de.schildbach.wallet
You can send money just by scanning a QR code the app displays. You need to install one of the QR code scanning apps for this to work (e.g. "Goggle").
The app currently only works for testnet. Because testnet is very slow in transaction processing, it currently takes ages to update the wallet. Unfortunately, I can't switch to prodnet, because Android apps only got 4 MB of heap memory and that's not enough for the blockchain. You can use the emulator and assign a max heap size of 32 MB though.
GPLv3'ed source available here: http://code.google.com/p/bitcoin-wallet/