The problem has multiple solutions depending on the environment.
Single system, no remote filesystems, no concerns for backups, and only one (or few) users, with no directories sharing owned files (such as video/audio files tend to be in a shared directory) is the easy one.
for each user, "usermod -u <newuid> -g<newgid> <username>"
This should work as long as the user is not logged in. You MIGHT have to modify the /etc/group file first (adding 500 to users groups, be sure not to do it to the system groups).
The manpage on usermod does say you have to modify ownership of cron jobs manually, but most users don't have a cron job in the first place.
Problems get more complex with directories that have files owned by multiple users. Sometimes such directories are owned by a project leader, and the leader makes the directory group writable which allows other users in the same group the ability to create files and directories in it. This causes problems because a simple usermod process will change the owner of ALL the files to the project leader, which is not what is desired. To handle this case you have to process each file separately and lookup the target UID based on the file/directory owner UID. (I used perl for the hash table lookups and access to the chown system call, but it could just as easily just add 500 to the current UID of the file and set that... but you have to be sure that the files original owner UID is >= 500).
This works... unless for some reason you already have a user whose UID is >= 1000.... The potential failure is that if the process gets interrupted for some reason, you can't tell if a UID that happens to be > 1000 is supposed to have 500 added to it or not when you restart.
This can be worked around by changing one UID at a time - start with the highest UID and work down - but it is much slower and requires a filesystem pass for each UID to be changed.
This works unless you have the cyclic problem, which for a beta I hope would not exist.
Handling remote fileservers, especially if those file servers support multiple systems... That is a totally different case and requires changing users on all systems.
As for the files /etc/login.defs and xxx.rpmnew - look at the differences and decide. Frequently there may be no difference. If the new one shows the UID/GID defaults >= 1000 and you accept the update... Just rename the new file to login.defs
I changed my uid's (after many hardware errors and failed repairs I got a new notebook that gets F16 right away, so the other systems needed to change).
Changing was very easy.
First I ran Bleachbit to erase some waste so the back-up image wouldn''t be unnecessary large.
After the back-up I booted to the emergency target / init 1 runlevel.
Then I first changed the group's gid with groupmod.
After that I modified my uid and gid with usermod.
Then I made sure that my /home was alright (not necessary but I gave it a chown -R :myusername /home/myusername)
I also checked my /tmp files and changed those that seemed important (although I don't think this is necessary either).
Next thing to figure out it is what else needs to be changed (or will preupgrade handle it from here), but first I'll be configuring Windows (takes me frigging a whole day to clean up al that crap they put on it) and installing F16.