I did some testing (changed the MAC, but instead of tethering, connected to my network at home and looked at the access log), and apparently the issue with my cellphone (and possibly anyone else who can change the MAC, but not connect), is that the MAC address is not "completely" changed. When I tried to connect my phone to my network, the router received requests from both its native MAC Address and the homepass one. Presumably, neither of those access requests had the "full" message, so the router thought both were garbage and returned an error to them.
So, it seems changing the wlan0 MAC Address using a terminal is not enough to change it completely, even temporarily. I can't think of anything else to do, really, other than maybe changing the very kernel of the phone to make it get the fake MAC from the get-go, if that's even possible.
Or maybe this is a consequence of changing the MAC without turning down the network before, but when the network is down the terminal just can't "see" wlan0 at all, it's as if it doesn't exist.
EDIT: Yep, it's exactly the latter. I managed to make it work on the weirdest fashion possible. I set up the MAC Address-changing command on the terminal, turned on the tethering and, before it had time to properly set up, pressed enter on the terminal, changing the MAC after wlan0 became available, but before the tethering started broadcasting. Not the easiest of methods, but seeing that green light is somewhat reassuring. Now, if I could just activate the tethering via the terminal...