Mensagem de erro "data: data inválida '2016-10-16'"

Hoje, meu relógio foi ajustado automaticamente para o horário de verão e um script de um crontab começou a falhar. Eu dei uma olhada no que estava acontecendo e o seguinte erro estava sendo exibido com LC_ALL=C:

data: data inválida '16/10/2016'

Eu pensei que seria melhor apenas reiniciar o sistema, mas agora eu reiniciei, e o erro ainda aparece:

$ date -d '2016-10-15'
Sat Oct 15 00:00:00 BRT 2016
$ date -d '2016-10-16'
date: data inválida “2016-10-16”
$ date -d '2016-10-17'
Mon Oct 17 00:00:00 BRST 2016

O que poderia estar causando isso?

O problema é que o horário de verão foi alterado e encaminhado 1 hora, em 16 de outubro de 2016, no seu fuso horário:

$ zdump -v America/Sao_Paulo | awk '/Oct 16/ && /2016/'
America/Sao_Paulo  Sun Oct 16 02:59:59 2016 UTC = Sat Oct 15 23:59:59 2016 BRT isdst=0
America/Sao_Paulo  Sun Oct 16 03:00:00 2016 UTC = Sun Oct 16 01:00:00 2016 BRST isdst=1

Assim, qualquer tempo entre 00:00a 00:59nesse dia é considerado inválido em seu fuso horário (mas talvez válida em outros):

$ TZ=America/Sao_Paulo gdate -d '2016-10-16 0:59'
gdate: invalid date ‘2016-10-16 0:59’

$ TZ=Asia/Ho_Chi_Minh gdate -d '2016-10-16 0:59'
Sun Oct 16 00:59:00 ICT 2016

Você pode definir um tempo adicional, que não está nesse intervalo:

$ TZ=America/Sao_Paulo gdate -d '2016-10-16 1:00'
Sun Oct 16 01:00:00 BRST 2016

O acima é comportamento de data do GNU.

A data do BSD não tem esse problema. Se a data de entrada for inválida no fuso horário, ela será ajustada silenciosamente por 1 hora até atingir um tempo válido:

$ TZ=America/Sao_Paulo date -j -f '%Y%m%d%H%M' 201610160000
Sun Oct 16 01:00:53 BRST 2016