How can two UProve token holders prove to a 3rd party that they aren't the same user?
The U-Prove Technology Overview V1.1 shows that this can be done. The issuer knows who the individual is but can't correlate that with verifier or prover use.

Upon setup the issuer can have extra attributes available that upon request of authorization from the prover the verifier can have access to. The verifier could use such an attribute and only successfully verify if it hasn't seen that attribute before.