Device tokens are not exactly unique per device; they're unique per operating system installation. So if a user buys a new device but does not restore from backup, then they'll get a new device token. And if a device is wiped, it will get a new device token, so the new user doesn't get the old user's messages.
In addition, there are different tokens returned for development apps using the sandbox and distribution apps using the production system.
Since a single user might have your app installed on multiple devices legally (iPhone and iPad, for instance), it will be much safer to have a many to many relationship between users and device tokens, to be on the safe side.
And since you mentioned Urban Airship, you might find that our alias feature helps for this sort of thing; you can assign a non-unique alias to the different tokens in our end, and then we'll keep track of the mapping between your users and their device tokens. See the registration and push parts of the UA documentation.
Edit: An update because I saw some more upvotes on this old answer. As of iOS 7, device tokens are unique for each application, even on the same device.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…