Ok. Ich hab mal nachgeforscht. Sudo wird für Ubuntu mit der Option --with-secure-path kompiliert, was bedeutet, dass die Umgebungsvariable PATH ignoriert wird, und stattdessen ein fest eingebauter Pfad benutzt wird.
Grund dafür ist wahrscheinlich, dass die PATH-Variable standardmäßig ~/bin am Anfang beinhaltet und ein Angreifer das zur Erhöhung der Privilegien nutzen könnte, indem er nach einem Einbruch in ein Benutzerkonto ein böses Programm bspw. nach ~/bin/apt-get kopieren könnte, was dann vielleicht schon bald vom regulären Benutzer mit Root-Rechten ausgeführt würde.
Es gibt aber auch Leute, die mit dieser Regelung nicht zufrieden sind, und das als "Wishlist-Bug" gemeldet haben: https://launchpad.net/distros/ubuntu/+source/sudo/+bug/50797
Ebenfalls aus dem Bugreport stammt der folgende Workaround:
sudo env PATH=$PATH <command>
Durch Eintrag folgender Zeile in ~/.bashrc kann man dieses Verhalten für sudo standardmäßig erzwingen:
alias sudo='sudo env PATH=$PATH'
Im übrigen verschiebe ich diesen Thread mal nach "Sicherheit".