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?
When you send a new transaction, using the old inputs, with a high(er) fee (you can send this even to another address of yourself), then this payment will be confirmed. At that time, when some pool wants to confirm your "old-low-fee" transaction this isn't going to happen, because the old inputs are already used. So it doesn't have to be the exact same amount and/or exact same address, it only needs the same inputs.
I think you were lucky two times here. I wouldn't send any coins to BTC-e after reading so many complaints and scam accusation against them here. They are using selective payments, they are selecting users which they pay and they have closed so many accounts without giving proper explanation why they did it, they have been neglecting emails and support is being not nice. There are other places to trade.
My experience in crypto was limited to setting up a GPU rig and ASIC butterfly rig a few years ago and scratching together a few coins. I've heard the occasional reports of pools or trading sites going down. BTC-e never crashed or stole my coins, albeit I usually didn't have any there or only traded for fun with a tiny amount. What is the best place to do this now? I haven't been active on any forums until I encountered the topic of this post, so I can just do research but I appreciate the heads up.
My personal experiences with Poloniex are good, I read good things about bittrex and bitstamp, but for all of them there are also people with negative experiences. Just be careful and look around on this board for recent posts about the different sites.