Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Since you can SSH over the LAN, it's almost certainly a router issue. I'd double-check that port 22 is forwarding correctly and that your SSH isn't using some other port. I'd also try forwarding a port other than 22 and trying to SSH over that (e.g., ssh -p 6789 me@remotemac). Note that if you don't want to reconfigure SSH to listen on a different port, you'll need to make sure that the router is forwarding external port 6789 (or whatever) to internal port 22.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.