Backup and restore  across domain  boundaries does not retain user security.

Well, when I restored  from stsadm, it kept both the sharepoint  security groups
previously defined in the portal, as well as the usernames in those groups (and
these usernames were in the form of firstdomain\login.
So apparently it seems to be retaining security of some sort..which may be
causing the problem..

Backing up and restoring across domains/forests will retain the user
info data, it just isn't usable as you have orphaned the SIDs.

You can export by site  excluding the '-includeuserpermissions' parameter
and only grab the content. Be aware this isn't a true backup  and restore
command as it misses many things like recycle bin, alerts, Web part
personalizations, etc. It also only works at the site level and not the
site collection  level.

You can always do an stsadm.exe -o migrateuser to re-sync the accounts
with a new user/SID

You do not want to add users  to the Web Application policies as this
OVERRIDES site  collection permissions, unless specifically required. You
want to use Site Collection/Site permissions.

If you backed up and restored  across domains (assuming different forest)
then you have orphaned the users' SIDS. Try the stsadm.exe -o
migrateuser command to resync with a new domain  account.