Indeed, U-Prove tokens are obtained using an advanced issuance protocol that results in “unlinkable” public key and issuer signature (these values are randomized by the user in the process). Since the issuer never sees these values, they cannot be used to track the user, even in collusion with the relying party (even if the issuer _is_ the relying party).
The video refers to our first U-Prove CTP. We recently released an update to the CTP, using the same architecture model but with a different client implementation. Details can be found on http://www.microsoft.com/u-prove; I encourage you to take a look at the white paper and the technology overview for more information.