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’
$ TZ=Asia/Ho_Chi_Minh gdate -d '2016-10-16 0:59'
Sun Oct 16 00:59:00 ICT 2016
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, if. If the input date is invalid in the timezone, it will be silently adjusted forwards 1 hour until it reaches a valid time:
$ TZ=America/Sao_Paulo date -j -f '%Y%m%d%H%M' 201610160000
Sun Oct 16 01:00:53 BRST 2016