I have just expereinced the same issue. I have a work around for you.
If you have a Snow Leopard Install CD you can boot from that by holding the C key upon boot up or hold down the option key and select the install CD.
Once launched select continue and then select your language. You will then have access to a tools/utilities menu where you can reset passwords. You select you System Disk and you will notice that you accounts are still missing however you should have access to re-set the root account / pw. Set it to a secure password - after all this is the highest level account on your machine.
Once done - restart into lion again and login into the root account. Username root with password you specified earlier. Once logged into the system - you should still find your old user folder still intact. I would suggest re-naming this account and add suffix _original if you intend on creating a new account with the same name. The username of the folder is based on the short name you input when you create an account.
You can then go into system preferences / users and groups and create a new account with the same short name. After this - I renamed the new user account to _delete and renamed my original account to its former name by removing the _original (as i kept the same short username) Log out and login with your original account - it may ask you to sync your keychain if you have changed your password from the original - in this case provide the previous password.
This worked for me - good luck.
I agree this is unaccaptable for Apple to release an upgrade with a bug like this. Good luck - hope it works for you