I've encountered this problem numerous times with old coins, but I've always been able to send regardless. I'm thinking this section is in need of an FAQ.
I suspect the issue may have to do with each Bitcoin wallet containing a unique set of unspent outputs. We could conceivably work around this on the client by forcing Electrum users to select higher than average fees or forcing prioritization of larger unspent outputs, but the way it works currently, users have more control over how coins are spent.
In any case, if your wallet gets stuck, consider taking the following two steps:
1. In the Receive tab (expert mode on), right-click on an address with more coins in it than you're trying to send, and click "Prioritize". Resend. This isn't especially fullproof if you've been reusing the same address to receive micropayments, but you probably haven't been doing that.
I'd estimate just doing step #1 has worked for me over 75% of the time.
2. If step #1 fails, *increase the fee*. Resend.
You should be okay. I don't think this is overly costly in terms of time or money, but we could conceivably handle the error in the GUI more gracefully, so that users aren't left with an indecipherable error code without any hint as to how they may work around it. A link to an FAQ at the least may help. I've been meaning to come up with one myself. Lots more documentation is needed. A significant amount of work has gone into the upcoming major release, and the Electrum community has really been innovating as of late on all aspects of the client.
Again, I suspect this "type -22" issue is encountered because each Electrum wallet history is unique. If you run Linux or Mac, on the command line you can check your wallet's unspent output tree for yourself by running `electrum listunspent`. You may find that your wallet has a higher number of low-value unspent transactions. You should be able to work around this in the GUI by either increasing the fee or prioritizing an address with a larger unspent transaction 'attached to it'.
I profusely apologize if this error cost you a trade. It should be an avoidable uncommon annoyance kind of thing now that you know how to work around it.
If I understood this correctly, is there any particular reason Electrum consistently forces the use of smaller outputs? And conversely, why doesn't the client notify the user of an insufficient transaction fee? (instead of resorting to an obscure error code)