It turns out that the response at the command line when you try to run rnv is completely misleading. It leads you to believe that the executable is missing, whereas it's clearly there. Actually the problem is caused by the fact that the rnv installed from the TEI repo is 32-bit, and won't run on a 64-bit kernel.
So instead of installing it from the repos, I'm downloading and building it instead:
apt-get install libexpat-dev wget http://downloads.sourceforge.net/project/rnv/Sources/1.7.10/rnv-1.7.10.zip unzip rnv-1.7.10.zip cd rnv-1.7.10 ./configure make make install
In view of this, I don't think rnv should be in the TEI repos at all, unless it can be done in such a way as to provide the right build for the host architecture.