Ok, I've got my head round part of this...

As you pointed out, the route command before was wrong...
I've now used "route add -net 172.20.2.0 gw 172.20.1.5 netmask 255.255.255.0 dev eth0"
(Note that I tried this before, but in a fit of stupidity I tried to use the 172.20.2.5 address for the new box, which is where the other route command appeared from!)

The new box is known as 172.20.1.5 (eth1) on the NAT network, and as 172.20.2.5 (eth0) on the new network.

I've also enabled routing by echoing 1 to /proc/sys/net/ipv4/ip_forward (was 0 by default)

The NAT box can ping anything on either network.
The new box can ping anything on either network (probably due to actually being on the other network vie eth1 and the 172.20.1.5 address)

Stuff on the new network can ping the NAT box and get onto the Internet (Primary aim achived)
Stuff on the old network cannot ping the rest of the 172.20.1.0 network (traceroute gives the 172.20.2.5 machine, then nothing past that (just * * *) even though the default route is to the 172.20.1.1 machine. Traceroute to 172.20.1.1 works fine)
Stuff on the NAT network can ping the new box as 172.20.2.5, but cannot ping anything else on the 172.20.2.0 network. (traceroute or ping give "Sendto: Host is down" messages)

Now, if this carries over to the ppp0 interface, then my primary goal is reached, however it would be nicer if both sides of the network could talk to each other properly...