Hi,
The computer you are trying to ssh into , should have the default gateway of the router.
Do you have a firewall enabled on the pc your ssh'ing from ?.
If so try disabling it.
When i have problems with routers, i usually make use of
http://hexillion.com/co/. Try to ping the public ip address from there.
Also make sure the router doesn't have a firewall enabled, some routers deny icmp packets, which is used by ping. Sometimes you have to manually allow ssh connections into your network on the router.
What kind of router do you have ?
Try telnetting into port 22 from your pc.
telnet publicip 22
Hope this helps :-)