cd não é um executável; é um shell embutido, portanto, o cd: command not found . Você também não está citando o comando sudo completo, por isso sudo está executando apenas a parte antes do && . Tente isto:
desc "Restart the application services"
task :restart, :roles => :app do
run "#{sudo} sh -c 'cd #{current_path} && bundle exec foreman export upstart'"
end
end
Você pode substituir sh pelo shell que preferir ou usar $SHELL se estiver definido.