This post is to help others who've encountered the same problem. I've been looking (Google'ing) around for quite some time and have just now come up with the solution. Tried to make the title Google-friendly
Ever since a week ago, I haven't been able to change anything in the file. Whenever I reboot my system, the file gets overwritten.
Just to be clear - the file is not wiped and restored to an original (clean) state, it's instead reverted to a previous state. Older hosts I've added to the file are still there, but I just can't add any new hosts to the file.
Also, if I "sudo gedit /etc/hosts", the changes are saved for that session. But once I reboot, they're gone.
Looking into the /etc folder, I've found a file called hosts.ac, which seemed like a copy of my hosts file. When I tried changing it - Presto! The /etc/hosts file was changed to reflect the content of this file.
After some investigation, seems this file was added after installing Cisco AnyConnect (hence the ".ac"), and on every reboot, it copies this file over /etc/hosts.
So if you have AnyConnect - in order to make changes to hosts, you need to edit /etc/hosts.ac, not the original /etc/hosts file!
Hope this helps someone - was a big mystery for me...