Again another dependent factor on how these companies operate is individually. Regardless that does suck but sadly Sony is a little different as far as Apple and Google go over seas and what not I think. They have independent businesses that operate on their own, where as Google and Apple propably operate all under the same roof.
Where as Sony, something could happen in Europe with their Playstation that may never actually happen over seas in NA. I was just going to tell you to try and call but apparently that didn't work.
Most I could suggest is possibly keep trying to call them back, it may seem like a pain but I have learned that it usually isn't more of a problem to do, it's more like that representative you were speaking with didn't want to go through the trouble. Sometimes if you keep talking to another, you'll eventually get one nice enough that will actually help you, actually know what they are talking about or possibly change your account location for you.
I don't know or you could call them and ask if there is anyway you can prove your location to them through ID or picture, license or something.. and they might then change the account region. Other than that I don't know what to tell you, it sucks but it's something that you gotta pay attention to with Sony although yes their systems aren't region locked, their companies operate individually and this can case account issues region wise.
I would just tell you to keep buying your games from wherever you used to buy them or make sure they don't have online codes, so they aren't from NA and they will work on your account. Order them online or whatever from where you used to buy them and they worked previously.
Or you could just buy your games used here, then spend the extra money that would've went towards the game towards an online pass that works with your Vita's region.
I moved to North America last year and was pumped to pick up a Vita when they launched, which I did. Shortly after setting it up I go to play one of my new Vita games online, pop in the stupid online code and what do you know? It doesn't recognise the code because it was bought in North America, but my account is Australian...
While I understand your frustration, this is more a matter of not having paid attention to the way Sony works; downloadable / redeemable content has always been region locked. The PSP, for example, could not use stuff from regions other than the one the game belongs to. Furthermore, just look at PSN cards, there's a reason they sell cards specific to a country, that's because the codes belong to particular regions and they aren't interchangeable~.
I doubt Sony will change your account region, I just don't think they can. Think about it, your thropies, userd ID, etc are all tied to a specific region. It's not as simple as changing a variable, more than likely they aren't even on the same server, in this case, I'm afraid you are screwed~.