Building up on Doug's manual fix to the problem, I was actually able to automate the process pretty easily. I'm writing this for people who are new to this thread so bear with me while I repeat some things that some of you may already know.
First of all, we need to grab the wpa_gui application in order to replace the NetworkManager service.
sudo apt-get install wpagui
Then we need to edit the /etc/network/interfaces file.
sudo gedit /etc/network/interfaces
Replace everything in this file with:
iface lo inet loopback
iface mlan0 inet manual
iface default inet dhcp
The "auto mlan0" line is crucial here because it's what starts the wpa_supplicant daemon automatically at startup. Just like Doug's fix, we still set manual configuration to our mlan0 but instead now just point it to the wpa_supplicant.conf configuration. And the final important bit is that we want our internet to automatically acquire the dhcp from the router, so that's what the last line is doing.
We then go into /etc/wpa_supplicant/ to edit the configuration file.
sudo gedit /etc/wpa_supplicant/wpa_supplicant.conf
This configuration file is a big deal because it will contain network passwords. We want to edit this file initially, and then just relegate any future edits to strictly the GUI. To do that, add the following into the file.
Now in the terminal, run the following code to first add your user to the 'netdev' group and then lock this config file down.
sudo adduser YOUR_USER_NAME netdev
chmod 600 /etc/wpa_supplicant/wpa_supplicant.conf
The next order of business is to prevent NetworkManager from running on startup.
sudo mv /etc/init/network-manager.conf /etc/init/network-manager.conf-disabled
sudo mv /etc/xdg/autostart/nm-applet.desktop /etc/xdg/autostart/nm-applet.desktop.disabled
Finally, we want WPA_gui to start on boot. Since this app doesn't have a service, we just do this from Ubuntu's own Startup Applications tool. Just search for it in Dash Home, click 'Add', write 'wpa_gui -t' into the command section and call it WPA GUI (or anything you want). The -t option is important because it starts wpa_gui in the tray. Save and restart.
Start the gui tool through the icon. mlan0 should be visible under the Adapter list now. Click on 'Scan', select your network of choice, enter your password and watch it connect automatically. Once you're done changing settings, go to File->Save Configuration to save everything. Your Surface Pro will connect to your WiFi automatically from now on.
Thanks go out to XRunHProf's excellent post on configuring WPA on Debian for this.