It also means that if your phone is stolen, so are all the funds from your PC.

Though it can be annoying, I think having a separate mobile wallet and then refilling it from time to time is conceptually the simplest/robust/most secure approach.

Same here... 

'Sent' transactions are 'greyed', not broadcasted and stay for days. No idea what to do with it..

HTC Desire

Replied.  Basically, it doesn't ever seem like there's a problem to the user.. other than that the coins never show up in the receiving wallet.  There are connections, the send process looks to complete just like all the other times, just nothing actually happens.

That means the transaction was larger than 10 kB in size? With only 4 inputs I find this a little bit hard to believe... Either that or the following isn't correct (or there is a bug in the software):

Do you have a backup?  If so, revert to that.  If not, you need to reset your blockchain by going to reset in the preferences and then chosing the disconnect.  When the app reopens, it'll redownload the last 52 weeks of blockchain. [Happy Anniversary Goonie]

Once you're back to a state with no pending transactions, send yourself the whole balance to a different client (like your desktop/laptop).  The fee you tried to pay isn't actually 'paid' until its mined, so you won't lose that .0005.  Once you send that tx, it should successfully get relayed.  From there, you can use your other client to send the two transactions to their original targets.  It seems that by sending the whole balance to a single address, you're increasing the priority and reducing transaction size enough that it relays with no fee.

If you have many transactions using the app, while you're catching up, you'll want to close the app periodically using the disconnect option.  If not, it might crash out with an out of memory error.  When I say many, I'm talking over a 100 or 200.  I know many people don't use it very often, but I tend to use it for a lot of day to day stuff, so have a decent amount of transactions on it. 

Hmm, that's odd. For some reason the peer nodes must be rejecting the transaction, because it's very clearly sending and announcing the transactions multiple times.

What we really need to see now is a log from the other side.

mohawk38, do you have a synced Bitcoin-Qt client? If not, you can find me online at some point (I am TD in #bitcoin-dev and will be around for a few hours now, maybe again tomorrow during the day time Central European time) - then you can connect to my node.

I suspect this line is the smoking gun:

W/System.err(  817): 26823375 [PeerGroup-2-thread-4] WARN com.google.bitcoin.core.Peer - Received alert with invalid signature from peer Peer(bitseed.xf2.org/69.64.34.118:8333): URGENT: upgrade required, see http://bitcoin.org/dos for details

The alert does not have an invalid signature, so it indicates a problem I've seen hints of before - some old Android devices appear to have a broken BigInteger implementation that renders ECDSA calculations silently incorrect (!!!!)

If you have such a broken device, you may be simply unable to use any non-server side wallet with it. Even clients like BitcoinSpinner would be unable to operate correctly.

We still need to prove that this is the case. If there's a way to get a copy of the wallet I can check the signature myself, or you could connect to a node I run and I'd check debug.log for a signature verification error when you're around.

OK, first we need to figure out the problem.

Go into preferences (advanced) in your Bitcoin Wallet on the HTC Desire and set "trusted peer" to be the IP address of your computer with Bitcoin-Qt. Then use "disconnect" and restart the app. Now find the debug.log file on your desktop computer generated by Bitcoin-Qt and upload it somewhere we can see it. Look for errors talking about bad signatures.

Andreas will have to help you get the wallet off the device. I don't know how to do that. It should be possible though.

In any case, it would be a good idea to be able to encrypt the private keys: if your phone is rooted (and I would think that the intersection between people rooting their phones and people using bitcoins is not empty), another application is more likely to be able to access the wallet-protobuf content. And you could only allow backuping a wallet on the sdcard if the private keys are protected by a passphrase.