WiFi network not accessible with modified MAC address
After much searching, I came across this thread on the xda-developers forum where people seem to be having much of the same issue with a Nexus 4. After trying several of the proposed solutions in that thread, I came across one that worked!

It turns out that Android keeps a permanent record of the MAC in /persist/wifi/.macaddr. For some reason, it insists on using the MAC in that file whenever connecting to a wireless network. If you're on a rooted device, however, you can overwrite it with whatever MAC you want. Interestingly, this change will also persist across reboots!

So, without further ado, here's how you change the MAC permanently on an Android device (substitute 112233445566 with the MAC you want):

computer $ adb shell
android $ su
android # cd /persist/wifi
android # echo -n "112233445566" &gt; .macaddr
android # ^D
android $ ^D
computer $ adb reboot