I think I've discovered a bug in the 3.1 RC. If I add the various capabilities to create and manage users to a user role, the option to add a user doesn't appear in the left hand admin menu, but a the button does appear on the user listing page. However, when you click it you get the "You do not have sufficient permissions...." message.
I'm adding these capabilities to the editor role and I can see that they're correctly in the wp_user_roles option in the database, so the problem must be when the capabilities are checked.
I've used exactly the same code on a 3.04 installation and it works correctly, I think it's a bug. I'm happy to help fix it. Can anyone suggest a good place to start looking?