Ok well on my router i have a mac filter option in the firewall, basicly it has a list of mac addresses that I manually enter and when activated, only those devices are allowed to connect. It's possible that this could be the problem. I assume this is the same sort of thing on your router
To find out if this is the problem, log into your router and see if the mac filter is enabled and then see if you can add the cloned mac address that you have been trying to connect with, then try and change your mac address like you were doing previously and see if you can connect. or, change your mac and then log into the router and see if you can add the new mac to the filter, I don't think it should matter which way round you do it but sometimes these things have to be done a certain way.
I can't promise that macchanger at boot will work but I thought it might be worth a try in case your network card is refusing to change the mac once up and running, I'm still quite new to all this myself so just going with what i know and consider to be logical steps to undertake to try and find a solution for you.
# lol, sorry I didn't realise you were using that to signify root priviliges, at least i know when i see it posted on here from now on!