I have the same problem.
After reboot the "Internet Connection Sharing" doesn't start, its startup state set to Manual (Triggered).
But even if I start it manually or set startup state to "Automatic", the service starts and keeps working, but there is no Internet access in my home network until I disable and re-enable ICS on my WAN interface.
I triple checked this behavior by clean installation of W10 build 1607, it acts always the same. I tried different driver versions for my network adapters - default from Windows Update, latest version from Intel website and latest drivers provided by my laptop manufacturer - the problem still exists.
I also made a clean installation of W10 build 1511 and the Internet Connection Sharing was working perfect, until I installed the Anniversary Update. After upgrade, ICS service startup state was set to "Automatic" and it was started on system startup, but the internet access in my home network didn't work until disabling/re-enabling the ICS on WAN interface.
Funny thing - Internet Connection Sharing definitely worked just fine on my old laptop with Windows 10 build 1607, but now I sold it and I there's no way to find a difference in configuration to figure out the problem. I faced this problem only after I bought my current laptop (Dell Precison M4800) a week ago. But since I tried clean Windows installation and different drivers I don't think its related only to my computer, especially because there are another people having this problem after Anniversary Update:
So reverting to Win10 build 1511 seems to be the only solution at the moment.
UPD: Here is a workaround - you can schedule running a script each time the computer starts, which will disable and re-enable ICS on desired interfaces.
You can take a script from this thread: How to enable Internet Connection Sharing using command line?