I am surprised that Electrum doesn't correctly calculate the minimum fee in the way the reference client does, as it has been around quite a while. In fact, they removed the enforced (and usually incorrect) fee:
https://github.com/spesmilo/electrum/commit/67d2b940bceaa6e2d5111ad6df51d0b542c837e3, which is the wrong way to go if you don't want users to have a bad time.
I see that you
re-spent the transaction and it was confirmed quickly with a 0.0080 fee. The minimum fee, so that the rest of the network doesn't just discard your transaction, would have been 0.0037 BTC, based on the size.
Use of Electrum also will almost double fees you need to spend, since deterministic wallets are created with uncompressed addresses, which makes spending your money take more data. Your address
electum 1.9 (the upcoming release) will use BIP32, and therefore compressed keys
I use Bitcoin-qt. It can send with the exact minimum fee required and does not let you send with less. Fees are calculated the way that relay nodes and miners calculate what is required, because they also run bitcoin.
