I looked at the TWRP sources for fix permissions and indeed this looks like it does what you are looking for - it reads the package listing in /data/system/packages.xml and then enforces the uid/gid information found there on each app data folder.
My c++ reading skills aren't all they should be, but I note there is a place in there involving multi-user where the coder punted a little bit. Given that 4.2 is potentially multiuser (do you have more than one user set up?), I suppose YMMV.
Take a Android backup before you run fix permissions in the recovery; that way you can always revert if you don't care for the result.
I started comparing the uids as you suggested, but there were just too many. It would have taken ages.
After seeing your comment update, I decided to go for it. I do not have more than one user.
I allowed the OTA update to 4.2.2 (I had flashed back to 4.2.1 stock), rooted and flashed TWRP.
I was still getting the UID error so I did as you said and took a backup in TWRP and then let it do its thing.
- all UIDs now fixed.
Once again, thank you for the help.
Just one last question, because I am a bit confused:
What did you mean by "Probably it is a bit safer to do this via adb in recovery...".
If I put the Nexus in Recovery mode, I cannot connect via ADB. Or did you mean something else?