Edit: I HAVE A SOLUTION!
1. create a nin account on the original region (if already changed just restore a backup)
2. set date & time, go into eshop and login, make sure you are asked for a password and logged correctly
3. change region, update the system and DO NOT FORMAT
4. as is now, set the correct date & time, go to eshop and login into account made in the previous region, if password window does not pop up, try to update some game if that does not work go to profile and change the country and retry logging into eshop or via game update.
If all goes well you will successfully login but it will throw you out to the home screen giving a region mismatch error.
5. now do format via settings, set the correct time & date and create a new nin account
Tried on 3DS and 3DS LL today.
If does not work with the first try just restore the stock nand and try again, but if you do all as listed if should go fine first try.