So Jesse discovered a solution and I'm going to share it here in answer form as clearly as I can muster. This fixed wifi for me using a Panda Wireless USB wifi adapter on Ubuntu 17.04:
For privacy reasons, the default settings for Ubuntu 17.04's network manager (ALL flavours, not just GNOME) cause the MAC address of the Wifi device to change constantly. To fix this, you just have to edit a config file and then restart the network-manager service.
Open a terminal and run:
gksu gedit /etc/NetworkManager/NetworkManager.conf
(On Ubuntu Mate it should be pluma instead of gedit; use kate on Kubuntu, leafpad on Lubuntu and mousepad on Xubuntu) list of default text editors
At the bottom of this file, copy and paste the following:
[device]
wifi.scan-rand-mac-address=no
Your final results should look something like this:

Then just save and close the file and run:
sudo service network-manager restart
And wifi should work again! (unless something else is wrong)
This fix should work even on a live CD/USB session.
According to the NetworkManager.conf manpage /etc/NetworkManager/NetworkManager.conf should not be modified as it will get overwritten on update. To make this change persistent you should make it in a new .conf file under /etc/NetworkManager/conf.d, e.g. /etc/NetworkManager/conf.d/disable-random-mac.conf.