Acho que finalmente encontrei a causa do problema.
Depois de adicionar um novo nó, você precisa reiniciar o mestre de marionetes e depois dele começar a aplicar a configuração de nós.
Como reiniciar o mestre de marionetes:
Por padrão, a execução do comando puppet master iniciará um servidor mestre Puppet daemonizado em segundo plano. Para interromper o serviço, você precisa verificar a tabela de processos com algo como ps aux | fantoche grep, então mate o processo.