To install navit on gutsy, you need to have gutsy-backports in your sources to be able to install libgps
You can add the following line to /etc/apt/sources.list:

deb http://archive.ubuntu.com/ubuntu gutsy-backports universe
deb http://navit.latouche.info/ubuntu gutsy main

To import my gpg key:

gpg --recv-keys CB229096
gpg --export -a CB229096 | apt-key add -