Did you actually force the update to Office 2016? I had this same issue on 14.x about a month ago and the latest Office 2016 update solved it. I believe in Office 2016 you can force a direct update by going to File | Office Account in any application.