Backup your emuNAND with
https://github.com/d0k3/EmuNAND9Tool/releases (you can do it with EmuNAND Tool as well, they do the same thing but you can run emuNAND9 directly on the 3DS)
Here is the latest link to emuNAND Tool in case you want to use that instead:
http://filetrip.net/3ds-downloads/utilities/download-emunand-tool-1-0-3-f33079.html
After you have backed up your emuNAND, format it with
https://github.com/javimadgit/TinyFormat/releases (this will avoid deleting any files on your SD so you won't lose your saves and such)
Then set up your NNID again on emuNAND.
Lastly, restore your backup.
If you have a spare SD card you can set up emuNAND on it and link your NNID there and skip the whole backup/restore process. As long as Nintendo's servers sees the console as linked, it doesn't matter what NAND or SD card you use, as long as that NAND/SD belongs to the same console. Your NNID will start working again after you relink it to the console.
Sadly this is far from the behavior I'm seeing.
Basically I had a 2DS, Sys 9.2, emu 10.3, both linked.
Last night I unlinked/formatted sys, and updated emu to 10.4. I tried eshop, and got the error.
I formatted emunand and it seems to me its now using the same folder in Nintendo 3DS as now if I change Theme in emunand it breaks menuhax.
Eshop still refused to work. I used Tinyformat on Sysnand again and this triggered a new folder in Nintendo 3DS, so now they are separate.
Then I see your note about using a different card, perfect. I copy the emunand over to it, format emunand again, new folder created, eshop works.
I put back old card, no dice. It seems to be the eshop is also linked to the emunand existing in that specific Nintendo 3DS folder.
So folder 9011XXXXXX is emunand with games/saves but bad eshop.
e1b2xxxxx was the sysnand.
On the new card, e1b2xxx is now emunand and 0c09xxxx is the sysnand.
So I am thoroughly baffled.
I can stick 8GB card in, no games/saves but eshop works.
Switch to 32GB card, i have games/saves but eshop broken. Same physical device so the idea of having that linked with an NNID regardless of SYS/EMU seems to not be correct.
Can I dump the contents of 9011xxxx to e1b2xxxx and saves will work since still same NNID? How can I restore title history?
Edit: it figures I get it to work on my 2DS and not my daughter who wants it. I think I know the catch. I used TinyFormat on mine and this did not trigger a new Nintendo 3DS folder. I'll try it on hers and see how it goes.
Edit2: First 2ds still same behavior. If I run TinyFormat then Emunand creates a new Nintendo 3DS folder for settings and this is what screws it over.