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.