I've experienced the following problem on Ubuntu GNOME 16.10 and 17.04.
Using Gnome-Network-Manager (I don't want to use other tools) I have issues when I create a wifi hot-spot to allow my Android device to access wired Internet. Sometimes (usually after a fresh boot) the wifi hot-spot works. But after a short while (maybe 10 to 30 minutes), my Android system will disconnect. When I reconnect Android will say something like "Connected, no Internet", but the Internet is available.
This is not a problem with just one Android system or device, I have tested with various versions of Android (Samsung and CynagenMod) and a Mac Book. All with similar issues.
From the Android side it appears that the network signal strengths fluctuates significantly over time.
I have tried various network cards, the internal network card (Intel AC 7260) and a couple of USB network cards. All exhibit similar behavior.