After many hours of hard work, the relay server has been fully recoded. Before, it failed horribly, but with ZylonShield and many other things, I have finally put the connection issue to rest for good. You may notice that people have blue icons, and are connecting still, don't be shocked by this, as that is the relay server in action. If a user is blue, they might have a slightly higher ping to you, as their connection is being handled through the server, not directly client to client.
Sorry it took so long to implement this. If you are still having connection issues in-game, please let me know.
Thanks!
~RedEyes.