The new dedupe engine and UI landed on trunk (development part of our code repository) last week, and we’d be more than happy if you gave it a try on our CiviCRM 2.1 sandbox and let us know how it works for you.
The new dedupe, besides the engine changes described earlier, sports a new user interface. Navigate to Administer CiviCRM → Find and Merge Duplicate Contacts and check out the new admin screens.