I get this error message when I try to send the full balance from monero-wallet-cli / simplewallet. Reducing the amount to cover the fees makes the error message go away.
So does this simply mean "Your remaining balance is not enough to cover the fees" or is there something else wrong?