Intel Ethernet Network Adapter Doesn't work - Ubuntu 16.04
One solution to the problem that I found while solving something else - Installing Ubuntu 16.10 does the trick.
I saw that for another computer model, the Intel NUC, it was recommended to use Ubuntu 16.10 because 16.04 doesn't support Kaby Lake CPUs very well:
https://communities.intel.com/thread/114411
http://nucblog.net/2017/04/kaby-lake-i7-nuc-conclusions/
So I checked and this computer also has i7 7700K which is of the Kaby Lake series, i.e. does not work well with Ubuntu 16.04.
Installed 16.10 and everything worked properly.
Thanks for the help :)