Upgrade/downgrade the wallet and try to send the transaction again.
This problem appears to be occuring quite a lot with electron cash wallet at the moment, due to the network/servers/peers and the client itself being fairly unstable.
Thanks, it seems to be a common problem with the network. I haven't upgraded or downgraded yet because I think every new software version comes along with some uncertainty in security. I waited some hours and tried the transaction again - and it worked. Today I wanted to send another tx and I got the error again. Well, I will try again later.
I found This. It allows you to broadcast a transaction from Viabtc's site. You might want to look into it and see if that'll broadcast your transaction much more easily (if it's not a problem with the input/output scripts when the transaction is generated).