O que é um label em C?

O label é só um nome para identificar uma linha onde começa um trecho de código.

A ideia dele vem do uso do goto, o comando que faz um desvio do fluxo de execução de forma direta. Esse comando sempre vem seguido de um nome de label existente naquela função. Então você coloca um nome em algum lugar só para marcar que ali é o local do código onde começa um trecho e o goto fará o desvio justamente para a instrução que vem em primeiro lugar logo depois do label.

Note que depois do código compilado esse nome desaparece e no lugar é pego o endereço do local do código onde acontecerá o desvio.

Exemplo:

inicio: //isto é um label
    printf("Hello");
    goto inicio;

Coloquei no GitHub para referência futura.

Esse código fica escrevendo a palavra sem parar na tela porque toda vez que chegar nessa terceira linha manda desviar para a primeira, já que é o nome usado. Como label não existe de fato como fator de execução o comando a ser executado é o do printf() e depois cairá no goto novamente.

A sintaxe dele é o seu nome e em seguida :, assim não confunde com uma variável ou outro tipo de símbolo do código.

Fica claro que isso não gera escopo novo e uma das razões para não ser um bloco de comando. O código todo ali é uma coisa só, ele não se distingue de outras partes ali mesmo, diferente do uso das chaves que faz com que aqueles comando dentro delas sejam algo com um certo isolamento em certo ponto de vista e cria uma espécie de hierarquia no código tendo uma parte dentro de outra parte.

Um switch é um enorme goto calculado. Dependendo do valor encontrado ele dá um goto para um local diferente. O compilador monta uma tabela com os valores correspondentes e o local para onde deve desviar. Esse local que deve desviar é o label, apenas um nome que indica onde é esse local.

Mas que dentro do switch o label tem uma sintaxe ligeiramente diferente sempre começando com um case seguido de um valor que será usado para montar esse switch.

Percebeu que ele também usa os dois pontos igual ao label do goto? Ele não usa chaves, por isso não é gerado um bloco e comando novo. [E possível usar chaves lá dentro para gerar um bloco de comandos, mas isso é ortogonal, é um outro mecanismo não relacionado ao switch.

Acharam que a sintaxe ficava mais linear, afinal o switch é um caso especial do goto e que o bloco de comando, se necessário ainda poderia ser usado normalmente, e não precisaria forçar seu uso. Provavelmente daria um pouco mais de flexibilidade. De resto acho que tem explicação na pergunta original.

Para entender mais sobre o cálculo do goto leia Como funciona o switch por baixo dos panos?.