O problema é o horário de verão alterado e encaminhado em 1 hora, em 16 de outubro de 2016, no 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
Então, qualquer momento entre 00:00
to 00:59
nesse dia é considerado inválido em seu fuso horário (mas talvez seja válido 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 é o comportamento da 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 1 hora até atingir um horário válido:
$ TZ=America/Sao_Paulo date -j -f '%Y%m%d%H%M' 201610160000
Sun Oct 16 01:00:53 BRST 2016