Picking up where kurosagi's post left off (the part about reconfigure your internet connection)... After removing your network interfaces and rebooting, the order you reinstall your network interfaces is important.
After you reboot, go back to your System Preferences > Network. Click the + button at the bottom of the left column. On the window that comes up, choose Ethernet first! (Important! I chose Wi-fi first my initial time through, and it didn't fix the problem). Click Apply. Then click + again and add your wi-fi. Click apply again, and your wi-fi should connect.
At this point, I rebooted, and tried an App Store update again, and it worked!
If Ethernet is not an option on your drop-down, then close the settings, open up Multibeast, and install a network driver (for me it was the Intel1000 driver). Once you've installed the driver from Multibeast, reboot again. Then go back to System Preferences > Network, click the + and you should see Ethernet in the drop-down. Create Ethernet first, and then click Apply. Then go back and add Wi-fi.
The reason why you have to add Ethernet first (afaik) is to ensure it's set as en0.
Hope that helps someone!