I guess that you already know everything about this. However, here is a list of changes specific to me:

I wanted everything to be automatic: just /etc/init.d/nstxcd start and I should be ready to go
I use dnsmasq for local DNS proxy (with cacheing) so my configuration use /etc/resolv.conf-upstream

Server setup

More or less standard, expect for fact that my DNS server has multiple IP addresses and I do want to run bind on some of them. So I added something like:

# /etc/bind/named.conf
options {
    listen-on {
        1.2.3.4;
    }
}

Configuring nstx is straightforward:

# /etc/default/nstx
NSTX_DOMAIN="tunnel.example.com"
start_nstxd=yes
ifup_tun=tun0
NSTX_IFACE="1.2.3.4"

Rest of the setup is same as in original instructions.

Client setup

Here comes the fun part.

# /etc/network/interfaces
iface tun0 inet static
        address 10.0.0.2
        netmask 255.0.0.0
        mtu 500 # optional, may solve ssh problems
        post-up route add -host `grep nameserver /etc/resolv.conf-upstream |head -1|awk '{print $2}'` gw `netstat -rn | grep ^0.0.0.0 | awk '{ print $2 }'` ; route del default ; route add -net default gw 10.0.0.1
        post-down dhclient

post-up part is modified so that DNS server doesn't have to be in same network segment as my IP address (as it often isn't).

# /etc/default/nstx
NSTX_DOMAIN="tunnel.example.com"
NSTX_DNS_SERVER=`grep nameserver /etc/resolv.conf-upstream |head -1|awk '{print $2}'`
start_nstxcd=yes
ifup_tun=tun0

Since I don't want to start nstxcd on each startup (because I don't need it always) I did:

sudo update-rc.d -f nstx remove
sudo update-rc.d -f nstxc remove

With this, I can get IP address and just do /etc/init.d/nstxcd start and I'm ready to go...

IP over DNS

Server setup

Client setup