Have you tried to send smaller transactions? If you have had a bunch of small incoming transactions then you will have to send out the coins in smaller batches.
I tried sending 1-2 coins with the same fault, weird isint it?
I love this currency, but boy the wallet is really holding the price back bigtime.