Hey Scavis,
I had exactly the same problem a few weeks ago. After some email contact with the support team I solved it on my own (finally

). But I have to say that I have a NCSoft Master account. So if you have a masteracc this one could work too for you (btw I´m using a german client. I hope everything will be the same with your perhaps english one).
1. In the login screen press "Reset Password"
2. Now you should see a new screen where you have to put in your login name (the one with the old email adress) and press the send button.
3. After that a message appeared ( something with "...message has been sent..:" and (!!!
that´s the important part !!!))
"If your account is bound to ...Masteraccount....then please visit https://...". Ok, that one could be the reason, why I haven´t received a message.
4. I pressed the Https:// link in the message window and logged into my NC Mastersoft account.
After that I selected my GW acc and changed my password without having to know the old one.
I was confused for weeks about the first part of the message "An email has been sent" until I realized they havn´t sent an email.
Ciao
mocilo74