I had an absolute mare with this process so thought it worth sharing the experience incase anyone runs into the issues I did and it might them out get round them.
Background - I had a hotmail email account, but never owned a xbox, had any xbox/gold services etc, so a completely fresh UK based microsoft own hotmail account. The were no card or paypal attached to my account.
Step 1:
Went to cdkeys and bought 3x12month brazilian gold passes (which warn that they can not be redeemed anywhere but brazil).
Step 2:
Used my cyberghost (paid for) VPN service and set it one of the brazil servers, checked whatismyip address and made sure I was browsing with a brazilian IP.
Step 3:
Logged into the brazilian version of the xbox site (used chrome to translate/convert the language), tried to redeem any of the 3x codes I had for gold and apply them to my account. Xbox site REFUSED to take them, kept throwing up a generic error saying something of the lines of 'payment failed, please contact us'.
Step 4:
Kept the brazilian VPN up and contacted xbox support. Told them my problem, they said to give them the keys, they confirmed they were all valid and got me to try a few times to add them - they all failed. Spent THREE HOURS on live chat with them, with microsoft trying everything allegedly to try and sort it. They said the problem was because I had a UK hotmail account, not a brazillian account, and that brazil codes wouldn't work with a UK created hotmail account. They advised for me to change my hotmail/microsoft account settings all to brazil. I immediately clicked that they were going to kick me off unless I told them I was in brazil, and they then agreed trying to help, but told me I would need to change all my account settings inc delivery and billing address to my 'location in brazil'. They also advised as the system has been being abused that this is a new process to stop people from the UK adding brazilian codes to their accounts. None of this worked, so they said they'd escalate and contact me back within 72hrs.
Step 5:
72hrs later I contact support, they not made any progress (not done anything). I spend TWO hours on live chat, repeating everything I've already done, but this time also 'switching my account' from the UK to brazil as I'm promised this will fix it. I'm told it takes 24hrs to take effect.
Step 6:
24hrs later I still can't redeem codes with a now brazilian hotmail account, contact support, they say it should have never been switched to brazil, and switch it back to the uk and try again, but wait 24hrs first.
Step 7:
24hrs later I still can't add the codes via the brazilian website using the VPN. Contact support, spend ONE HOUR going round in circles and get cut off, rejoin the chat to a guy called 'owen'. He asks me what vpn I'm using, I go errrr errrr errr 'cyberhost', he says 'do me a favour and try again with tunnelbear, download it and try that instead'. He knows what I'm upto, so we continue without saying we both know what I'm upto, he's not falling for the 'I'm working in brazil routine'. I install tunnelbear, check whatismyip to make sure I've got the brazilian ip, try the brazil xbox site, and THE CODES WORK!!! So I apply them to my account, tell owen he is a legend, think I'm home and dry, end live chat, and drop the vpn and go to the GPU ultimate upgrade for £1 site.
Step 8:
My account refuses to upgrade the gold to ultimate, errors out saying the region isn't right on the store I'm using and doesn't match my gold codes. (I'm using the uk site to upgrade my brazilian codes, on my uk xbox account). I try everything to upgrade, try paypal, try different credit cards, allsorts. Refuses to upgrade my brazilian gold. I contact the dreaded support again. Spend ONE HOUR on live chat to support, they tell me you can't upgrade brazil codes from the uk to ultimate, they need to migrate my account back to brazil and then try. Wait 24hrs.
Step 9:
Wait 24hrs, same error, can't upgrade brazilian gold to GPU. Contact support and they tell me this is because I'm using a uk payment method, advise to delete all payment methods, convert account back to uk, wait 24hrs and then add paypal.
Step 10:
Wait 24hrs, same error, can't upgrade brazilian gold to GPU. Contact support and they say they know exactly what the issue is, it's because I have 36months of gold on my account, and you can NEVER upgrade 36months of gold to GPU, it's impossible, as part of the upgrade process, it adds on extra month, taking me to 37, and you can't upgrade 37months. They tell me that I need to wait 1 month, I'll have 35 months left of gold, then I can do a GPU upgrade. I think this is fishy, but take their word for it and drop the support.
Step 11:
I go away and do some reading and EVERYONE else is having no issues upgrading 36months of gold to GPU so I contact support and call bu11sh1t on them. They again repeat exactly the same line without being prompted 'YOU CANNOT UPGRADE 36MONTHS GOLD TO GPU'. I quit support and try a 3rd time with support, to see if I've just got some idiot support people and I just got unlucky dropping two of them. 3rd time in succession I get someone tell me straight away it's impossible to upgrade 36months gold. I'm proper gutted. So I try a different approach, and kick off at support saying this is utterly unacceptable, I've been given the runaround, I've wasted hours and hours, this is my first time using microsoft blah blah blah. I also tell them as I'd seen it mentioned somewhere in passing that they can delete brazil regional codes, and add general non-region codes onto your account. I DEMAND they do they, support do REALLY NOT WANT to do this, but as I'm losing it on them, they begrudging agree to replace my codes. Once he advises they've 'been replaced' (I didn't believe him), I try to do the GPU upgrade for £1 on my 36months of gold - TADAAAAAAA, it worked!! I told the bloke he's been very helpful, and I now have 36months of GPU. I don't call him out on his bu11sh1t re it being impossible to upgrade the 36 months as I'm just happy to be out of this nightmare.
So there you go. My experience. After hours and hours online to support, I'd have rather paid full price if had to do that again. So use tunnelbear een if you have another paid for VPN service like I did, maybe there's something fishy going on where ms 'approve' the tunnelbear IP, I don't know, but also, you might need to get them to replace your codes if it all goes wrong.
Good luck!!