Sorry, but the deb-rebuild does not work for me.
I have followed exactly the instructions, but I get:

root@pussy:/tmp/nfs-correct/nfs-utils-1.1.2# debuild -us -uc
(...)
dh_install
dh_installdocs -A
dh_installdocs -pnfs-common debian/README.Debian.nfsv4
install -m 0755 debian/nfs-common.init debian/nfs-common/etc/init.d/nfs-common
install -m 0755 debian/nfs-kernel-server.init debian/nfs-kernel-server/etc/init.d/nfs-kernel-server
dh_installman
dh_link
dh_installchangelogs ChangeLog
dh_strip
dh_compress
dh_fixperms
chmod u+s debian/nfs-common/sbin/mount.nfs
dh_installdeb
dh_shlibdeps
dpkg-shlibdeps: warning: debian/nfs-kernel-server/usr/sbin/rpc.svcgssd shouldn't be linked with libdl.so.2 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-kernel-server/usr/sbin/rpc.svcgssd shouldn't be linked with libldap_r-2.4.so.2 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-kernel-server/usr/sbin/rpc.svcgssd shouldn't be linked with libgssapi_krb5.so.2 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-kernel-server/usr/sbin/rpc.svcgssd shouldn't be linked with libkrb5.so.3 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-kernel-server/usr/sbin/rpc.svcgssd shouldn't be linked with libk5crypto.so.3 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-kernel-server/usr/sbin/rpc.svcgssd shouldn't be linked with libcom_err.so.2 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-kernel-server/usr/sbin/exportfs shouldn't be linked with libwrap.so.0 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-common/usr/sbin/rpc.gssd shouldn't be linked with libdl.so.2 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-common/usr/sbin/rpc.gssd shouldn't be linked with libgssapi_krb5.so.2 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-common/usr/sbin/rpc.gssd shouldn't be linked with libk5crypto.so.3 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-common/usr/sbin/rpc.idmapd shouldn't be linked with libnsl.so.1 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-common/usr/sbin/rpc.idmapd shouldn't be linked with librt.so.1 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-common/usr/sbin/rpc.idmapd shouldn't be linked with libresolv.so.2 (it uses none of its symbols).
dpkg-shlibdeps: warning: debian/nfs-common/usr/sbin/rpc.idmapd shouldn't be linked with libldap_r-2.4.so.2 (it uses none of its symbols).
dh_gencontrol
dh_md5sums
dh_builddeb
warning, `debian/nfs-kernel-server/DEBIAN/control' contains user-defined field `Original-Maintainer'
dpkg-deb: ignoring 1 warnings about the control file(s)
dpkg-deb: building package `nfs-kernel-server' in `../nfs-kernel-server_1.1.2-2ubuntu2.1_amd64.deb'.
warning, `debian/nfs-common/DEBIAN/control' contains user-defined field `Original-Maintainer'
dpkg-deb: ignoring 1 warnings about the control file(s)
dpkg-deb: building package `nfs-common' in `../nfs-common_1.1.2-2ubuntu2.1_amd64.deb'.
 dpkg-genchanges
dpkg-genchanges: not including original source code in upload
dpkg-buildpackage (debuild emulation): binary and diff upload (original source NOT included)

And then there is no resulting *.deb file.

Anyway, I found:

root@pussy:/tmp/nfs-correct/nfs-utils-1.1.2# ll $(find . -name mount.nfs)
-rwsr-xr-x root     root              76,088 2008-06-03 18:28:19 ./debian/nfs-common/sbin/mount.nfs
-r-s--x--x root     root             268,256 2008-06-03 18:28:18 ./debian/tmp/sbin/mount.nfs
-rwxr-xr-x root     root             268,256 2008-06-03 18:28:15 ./utils/mount/mount.nfs


But these new binaries still will not work out of the box:

root@pussy:/tmp/nfs-correct/nfs-utils-1.1.2# ./debian/nfs-common/sbin/mount.nfs rusnas1a-n1:/vol/rusnas1a_n1_vol3/sw /nfs/rusnas/sw
mount.nfs: not using string
mount.nfs: mount to NFS server 'rusnas1a-n1' failed: timed out, retrying
mount.nfs: mount to NFS server 'rusnas1a-n1' failed: timed out, retrying
mount.nfs: mount to NFS server 'rusnas1a-n1' failed: timed out, retrying


Only when I set manually -o proto=tcp the nfs-mount works:

root@pussy:/tmp/nfs-correct/nfs-utils-1.1.2# ./debian/nfs-common/sbin/mount.nfs rusnas1a-n1:/vol/rusnas1a_n1_vol3/sw /nfs/rusnas/sw -o proto=tcp
mount.nfs: not using string

root@pussy:/tmp/nfs-correct/nfs-utils-1.1.2# mount | grep rusnas
rusnas1a-n1:/vol/rusnas1a_n1_vol3/sw on /nfs/rusnas/sw type nfs (rw,proto=tcp,addr=129.69.201.80)