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
1HxCHN8tVMUpqX1j3y9iR3bLgxKed6eB7k
is uncompressed, as I can see by it's 130 char hex pubkey:
046c6e5f74d644afb72679dbb27355817b5c15adf2859f6864d4e1e0133435cecf9d77828739e70
91f9ca7903f5b87cbb60fa36bd3b287c20c7c7398ec90404b12
The newest version was supposed to support BIP32, which would create compressed addresses for new wallets, but I can find no changelog docs supporting this:
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.