I have just thought of a couple of things that may help...

You can group your users into groups, either via AD (if you have it) or using Local Users and Groups if the server is in a workgroup. It may be easier to put the required users into a single group and grant that group access to the database. Where different levels of access are required, create and assign differing groups accordingly. If the SQL Server users were created from Windows logins, the issue with SIDs becomes moot, saving alot of trouble. If not, then I would simply delete/remove the accounts from the database and recreate them.

The point here is that the SID in itself is not necessary, it is the user that counts. So instead of finding the SID of a user and recreating it, simply remove the user and then create a new login and the associated mappings.

As long as you can restore the database without errors, this may be your fastest route back to it being usable.