Remote access beyond your router

This is a nice tutorial on how to use NXserver and sshd in Ubuntu to connect to a remote computer anywhere in the world.
Strangely though, I seem to be falling at the first hurdle here as in the section called "STEP 1: Testing SSH", I get this

$ ssh localhost
The authenticity of host 'localhost (127.0.0.1)' can't be established.
RSA key fingerprint is 5e:13:99:b5:12:51:9c:1e:99:8e:25:ec:ef:42:33:ad.
Are you sure you want to continue connecting (yes/no)? yes
Failed to add the host to the list of known hosts (/home/paul/.ssh/known_hosts).
paul@localhost's password:
Linux ubuntu-mac 2.6.26-5-generic #1 SMP Sun Aug 3 01:25:54 UTC 2008 i686

The programs included with the Ubuntu system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.

Ubuntu comes with ABSOLUTELY NO WARRANTY, to the extent permitted by
applicable law.

To access official Ubuntu documentation, please visit:
http://help.ubuntu.com/
Last login: Mon Aug 4 23:32:31 2008 from localhost

Then, as per the tutorial, I type

ssh paul@xxx.xxx.xxx.xxx (where the x's represent my external IP)

and get this after quite a delay

ssh: connect to host xxx.xxx.xxx.xxx port 22: Connection timed out

Actually, I really don't understand this last command and maybe I've misinterpreted it. Right now it looks like I'm trying to ssh from Ubuntu on my Mac back to Ubuntu on my Mac. Doesn't seem right.