After trying many of these solutions, I was going to just delete my current AVD and make it again, but when I clicked the down arrow on the AVD, I noticed "Cold Boot Now".
On a whim I tried that. Lo and behold my emulator has internet connectivity again!
EDIT: Ok, for those saying why not just wipe data and restart. Do you reformat your PC every time you restart it? Wiping data on the emulator is just like doing a factory reset to a phone or reformatting your hard drive on your PC and reinstalling your OS. It is unnecessary unless the data is totally corrupt.
When you shut off the emulator and restart it, it is like putting your PC in hibernate or sleep mode. Memory is not wiped, it is saved.
Doing a cold boot is the same as rebooting your phone or rebooting your PC. It resets memory and lets things reload. This allows the network emulation to start with clean memory and connect properly.
So, don't wipe your data. Just cold boot. If it still doesn't work, then wipe, but save that as a last resort.