This seems to work much better with SQL/MSDE 2000. Here's what I did...

1) Restore the database

2) Add the login (not giving access yet to the db)

3) run sp_change_users_login 'UPDATE_ONE', ...

4) (if #3 was successful, now the login has access to the db)

Regarding the docs on sp's that I did not have, this is not installed by default for SQL7 (but I think it is downloadable). On the other hand, the docs for sp's are installed by default for SQL 2000.