1. Open Internet Explorer [Even if you use Firefox - open IE]
2. Click Tools -> Internet Options -> Connections tab -> Hit LAN Settings
3. Uncheck the box that says " Use a BAD BAD BAD for your LAN setting "
4. Reopen maplestory [Either through Firefox/IE/gamelauncher.exe]
And it should work :)
Credit to pikmintaro for posting the solution here:
http://forum.nexon.net/MapleStory/forums/thread/7712022.aspx