O problema foi com o meu peixe shell aka user friendly (não muito amigável desta vez, não é?) shell. Por alguma razão, parecia que o comando sudo era cada vez diferente de sessões diferentes. Adicionando
Defaults !tty_tickets
no arquivo sudoers (como descrito link ) resolveu o problema. Veja o link acima para as informações de adição.
Obrigado a todos por sua atenção sem que eu não conseguisse entender a situação.