Apenas no caso de ajudar alguém, foi o cabo USB. Irritantemente os cabos que eu tenho da Samsung (um para o meu tablet, um para o meu telefone) parecem ser específicos do dispositivo e obtê-los misturados produzirá o erro acima e o dispositivo não conectará.
Seria bom se o erro fosse um pouco mais amigável, mas pelo menos por enquanto esta resposta está aqui para ajudar qualquer outra pessoa que veja esse problema.