Is this a store bought router?
Even if it is not if you have the port 22 open and being forwarding to the internal IP and port of the machine and the machine's port is open ( which appears to be since you can connect local ), then it should work.
Things to try.
From the network use one of those post checking sites like http://www.hackerwatch.org/probe/
and scan for port 22 and see if it open.
One thing it can be is the provider you are using is blocking common ports to stop an end user from running a server. Some charge to allow you to have normal access to your own stuff. One way around this is the following. On the router use port 10000 and forwarded it to your internal lan machine port 22.
Ext IP, port 10000 ---> Int IP, port 22
Distribution: RHEL 5.1 with Pieces of this and that.
Kernel 184.108.40.206, KDE 3.5.8 and KDE 4.0 beta, Plus Development src.rpm, ATI fglrx64_7_1_0-8.433-1 rpm with 3D and DRI working.
Acer 5100-5840 with webcam, ati, sdcard reader, sound, atheros based wireless, all working. Only thing not working is the memory stick reader.