Assuming you are using the Bitcoin Core wallet...
If your transaction is not showing on any of the block explorers, then first of all don't worry, you still have your coins in your wallet. They just aren't showing, but they are there with your private keys, of that I am fairly certain.
To get them to show up in your wallet, I think you need to quit the wallet, then delete it's local mempool file (will be in your file system somewhere, probably in the same directory as your wallet.dat file). Then restart your wallet with -walletbroadcast=0 (if you are on a mac use the command line / terminal "open /Applications/bitcoin-qt.app --args -walletbroadcast=0"). Then you should be able to right-click and "abandon transaction" on the transaction in the transactions tab.
I think this is what I did, though I may have had to restart the wallet after also.
As for the error you got from pushtx, regardless of whether your fee is high enough or not to get confirmed, this is strange to me, having too low a transaction fee shouldn't prevent your transaction from showing up in block explorers. It would only explain why a transaction hasn't been confirmed yet. So I don't understand this part.
Maybe someone with more knowledge can help.
(I have a similar problem with my transaction not getting into the mempools but the error i get is different, i'm told "missing parent". If anyone can help my thread is here:
https://bitcointalksearch.org/topic/bitcoin-core-transaction-not-reaching-mempools-missing-parents-2637574.