Nós nos deparamos com esse problema ao atualizar para o Jenkins 2.60.1. Essa versão é a primeira versão LTS a requerer o Java 8 e nos certificamos de atualizar o mestre para usar o Java 8. Infelizmente, os escravos não começariam, dando o erro que você reporta no título.
O problema era que os nós escravos estavam começando a usar o Java 7 e tivemos que usar o botão "Avançado" na página de configuração do nó para garantir que o caminho Java correto fosse usado pelos nós escravos