Hi,
I had this exact problem. I installed the 10.6.5 update and when I finally rebooted several days later, all non-system users on my machine were deleted. Only "Other" showed up in the login screen. While the users were removed from the Directory Services, their data was still intact though, as their home directories in /Users were unchanged. This is of course a big relief...
After reading this thread and the pages mentioned here, I came up with the following solution. Please replace "username" with the short (Unix) name of your user account (i.e. the one without spaces).
1. Start the computer in Single-User Mode, by holding down Command+S as it boots up. You end up in a terminal as the root user.
2. As suggested on the screen, do the following to check and mount your filesystem:
/sbin/fsck -fy
/sbin/mount -uw /
3. Find out which accounts have been deleted (here I assume 'username' is one of them):
defaults read /Library/Preferences/com.apple.preferences.accounts
4. Convince yourself that the user data is still safe:
ls /Users/username
5. I noticed that the 10.6.5 update made backups of the Directory Services and shadow passwords in /private/var/db as the xar archives 'dslocal-backup.xar' and 'shadow-backup.xar', respectively. If you also have these files, you are in luck! Restore the settings for each deleted user, as well as all shadow passwords, as follows:
cd /private/var/db
xar -xf dslocal-backup.xar dslocal/nodes/Default/users/username.plist
xar -xf shadow-backup.xar
6. For good measure, remove the record of deleted users (not sure if this is necessary, but seemed like a good idea at the time):
rm /Library/Preferences/com.apple.preferences.accounts
7. Restart the computer:
shutdown -r now
I restored the settings for all deleted users in Step 5, and everyone was back after the reboot. The great thing is that all settings are restored the way they were, including the password, user GUID (which should prevent Time Machine from redoing a full backup as mentioned in this thread) and the login picture (which was stored in the JPEGPhoto field in the plist file and would have been lost otherwise).
Of course, this solution might not apply to your specific problem, so please take care when you tamper with system settings via Single-User Mode.