So far it sounds like a bug in the Android client's handling of very small ("spammy") transactions, which do require a fee to be safe. Note that the rules are complex, and include not just how many bitcoins were transferred, but how old those bitcoins are, since spammers will presumably find it easier to spam with new coins.
Very-low-priority transactions will get dropped by peers, because they look like "spam" transactions and network bandwidth is not free.
I don't know if the current rules are written down anywhere besides the source code; improving the fee-handling and spam-detecting code in bitcoin is high on my bitcoin improvement wish-list, so if they were written down they'd be likely to change fairly soon...
Some detail is given in the wiki:
Transaction fees - BitcoinI'm not sure if it is all on the right track, and it is clearly a bit out-of-date.