Any tx's with outputs <= 0.001 BTC require a fee. Until recently i was not aware of this and the both the android and iPhone app do not factor this in when calculating the tx fee (the web interface does). Eligius does process low fee transactions for blockchain.info but there can be a delay of up to a few hours.
I see, thanks. Strange though because I sent another
transaction later of 0.1 BTC and this time it did ask me to add a 0.005 fee. Was that for a different reason than the <= 0.001 BTC output rule?
Now I have another problem though. I'm tying to send a third transaction of 0.2 BTC from the same paper wallet
address, but after I scan the QR code it says 'Insufficient Funds'. There's 5 BTC there so something must be going wonky. At first I thought maybe I had to wait for confirmations from the previous
transaction, but it has over 100 now.
If you see the transaction on blockchain.info is has been transferred and should be added to a block, but if on blockchain.info it says that it is a "low priority transaction" it can take some time, usually only a few hours. There is a branch of the desktop client that will ignore the fee rules and send a transaction without any fee and you can get stale transaction that no one will add. I know you can use pywallet to remove those from a wallet, but I don't know how you could remove one from an online wallet.