The -zapwallettxes fix worked! Thanks for all the advice. The coins are now back, safe and sound. I'm assuming that I don't have to re-send if I don't want to without messing anything up, right? It was going to BTC-e for trading the dump.
You have to realise your old transaction will probably still exist in the mempool of several nodes.
It means there is still a chance this old transaction will be confirmed. If you want to avoid this at all costs (even if the odds are small), you have to re-use the unconfirmed outputs as input for a higher fee transaction.
Excuse my ignorance please. What exactly does it mean to "Re-use the unconfirmed outputs as input"? How does one go about doing this? Is it simply to send the exact same amount to the exact same address with higher fee or something a bit less straightforward?