Pode ser um problema de caminho, tente
sudo /usr/bin/apt-get ...
Você pode definir o caminho que o sudo pesquisará com a diretiva secure_path
no arquivo sudoers
secure_path
Path used for every command run from sudo. If you don’t trust the people running sudo to have a sane PATH environment variable you may want to use this. Another use is if you want to have the "root path" be separate from the "user path." Users in the group specified by the exempt_group option are not affected by secure_path. This is not set by default.