Assuming you have an Active Directory environment:
I believe the backslash format DOMAIN\USERNAME will search domain DOMAIN for a user object whose SAM Account Name is USERNAME.
The UPN format username@domain will search the forest for a user object whose User Principle Name is username@domain.
Now, NORMALLY a user account with a SAM Account Name of USERNAME has a UPN of USERNAME@DOMAIN, so either format should locate the same account, at least provided the AD is fully functional. If there are replication issues or you can't reach a global catalog, the backslash format might work in cases where the UPN format will fail. There may also be (abnormal) conditions under which the reverse applies - perhaps if no domain controllers can be reached for the target domain, for example.
However: you can also explicitly configure a user account to have a UPN whose username component is different from the SAM Account Name and whose domain component is different from the name of the domain.
The Account tab in Active Directory Users and Computers shows the UPN under the heading "User logon name" and the SAM Account Name under the heading "User logon name (pre-Windows 2000)". So if you are having trouble with particular users I would check that there aren't any discrepancies between these two values.
Note: it is possible that additional searches are done if the search I describe above doesn't find the user account. For example, perhaps the specified username is converted into the other format (in the obvious way) to see if that produces a match. There must also be some procedure for finding accounts in trusted domains that are not in the forest. I don't know where/whether the exact behaviour is documented.
Just to further complicate troubleshooting, Windows clients will by default cache information about successful interactive logons, so that you may be able to log into the same client even if your user account information in the Active Directory is inaccessible.