[quote]So how do you encrypt this UUID?[/quote]
You don't. It's just a GUID or some other low collision rate hash.
[quote]And what do you send for a password reset?[/quote]
You send them a new UUID in a link. When the link is hit, the UUID resolves back to their account and they are directed to enter a new password, just like a first time user.
The combination of time (the UUID can be time boxed), activity (a successful login nullifies the UUID), and possession (control of the account's registered email address), and if you want to get really wild, knowledge of a security question, creates a scenario where there are no good purely technical solutions for the attacker.
An attacker could, in theory, create a colliding GUID for an account they know the name of (but not password), manually enter the UUID link, and set the new password (assuming there is no security question).
But if an attacker manages to consistently generate colliding GUIDs*, they have accomplished something so monumental that they should be heralded as the second coming of Steve Jobs or something.
(*Assuming the coders didn't decide to come up with their own GUID generation algorithm that is easily reverse engineered and seeded)