The problem is the daylight saving time changed and forwarded 1 hour, on 16 October 2016 in your timezone:
$ 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
So any time between 00:00 to 00:59 on that day is considered invalid in your timezone (but maybe valid in others):
$ TZ=America/Sao_Paulo gdate -d '2016-10-16 0:59'
gdate: invalid date ‘2016-10-16 0:59’
You can set additional time, which isn't in that range:
$ TZ=America/Sao_Paulo gdate -d '2016-10-16 1:00'
Sun Oct 16 01:00:00 BRST 2016
The above is GNU date behavior.
BSD date does not have this problem, it set the correct date value automatically if current date is invalid in the timezone:
$ TZ=America/Sao_Paulo date -j -f '%Y%m%d%H%M' 201610160000
Sun Oct 16 01:00:53 BRST 2016