After changing your MAC Address - did you restart your modem, or other connection?
A cable modem, for example, will be tied to only one MAC address at a time. Restarting the cable modem will reset that 'tie', and the modem should then connect with the new MAC address.
You might also have an internet supplier who requires you to contact the supplier with your change of MAC address - but usually a restart of the modem is all that's required.
If you are NOT connecting directly to the router, then also try restarting your router, which is the device actually used to share your internet connection.
Serendipity is a lucky guess !