It only shows that error if the user can't be found. Are you sure the username and email address were entered correctly? Try selecting both "Lost Username" and "Lost Password" then enter the username of the account you're trying to reset.
Have retested and appears to be working fine in my tests. It's possible your users maybe out of sync if you're not registering them through CB. Try running the Synchronize Users tool within CB > Tools and retrying.