I have redone the setup using ubuntu 12.04 and it's looks the same. Below is the iptables settings on my ubuntu gateway 254.17

Code:
ubuntu@ip-192-168-254-17:~$ sudo iptables -nL -v -t nat  --line-numbers
Chain PREROUTING (policy ACCEPT 0 packets, 0 bytes)
num   pkts bytes target     prot opt in     out     source               destination         

Chain INPUT (policy ACCEPT 0 packets, 0 bytes)
num   pkts bytes target     prot opt in     out     source               destination         

Chain OUTPUT (policy ACCEPT 0 packets, 0 bytes)
num   pkts bytes target     prot opt in     out     source               destination         

Chain POSTROUTING (policy ACCEPT 0 packets, 0 bytes)
num   pkts bytes target     prot opt in     out     source               destination         
1        0     0 MASQUERADE  all  --  *      *       172.25.38.0/24       0.0.0.0/0
Below is the route settings on the box(254.21) behind the ubuntu gateway
Code:
ubuntu@ip-192-168-254-21:~$ route -n
Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
0.0.0.0         192.168.254.1   0.0.0.0         UG    100    0        0 eth0
172.25.38.0     192.168.254.17  255.255.255.0   UG    0      0        0 eth0
192.168.254.0   0.0.0.0         255.255.255.0   U     0      0        0 eth0
A tcpdump on the 254.21 shows the same output

Code:
ubuntu@ip-192-168-254-21:~$ sudo tcpdump host 192.168.254.17
tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on eth0, link-type EN10MB (Ethernet), capture size 65535 bytes
14:31:29.775917 ARP, Request who-has 192.168.254.17 tell localhost, length 28
14:31:29.776034 ARP, Reply 192.168.254.17 is-at 12:f4:31:06:e3:d3 (oui Unknown), length 28
^C
2 packets captured
2 packets received by filter
0 packets dropped by kernel
Kindly see whether I am leaving anything out. Thanks