Update: I fixed my problem last night on my own! Thanks anyways.
Apparently the "Network Connections" GUI is fudged when it comes to spoofing your MAC address.
The solution (what I did to get it to work):
Open a terminal, become the root, and type the following:
Right click on the network connections -> disable (both Wireless/wired)
- ifconfig wlan0 down (turns off the Wireless device
- ifconfig wlan0 hw ether 00:00:00:00:00:00 (the very end is the new MAC address you want to use
- ifconfig wlan0 up (turns ON the Wireless device
Right click on the network connections -> enable, and presto! It works great!