@addamnorth
Yes, this issue was reported a couple of times here in the forum. if you go to tags (the icon right of the clock symbol on top) and select Android you will find the descriptions of similar problems.
It is happens, when the total size of a transaction becomes to large, typically caused by a large number of small transactions used to compose the outgoing transaction.
It helps to send the coins in smaller amounts. Typically a transaction of 6k-7k makes it to the block chain without problems.