Cannot delete a user

Login as admin user. Create a new user. Logout and login as the new user, fine. Logout and login as admin user and delete the new user. Get the error:

Can not delete user

Sorry; we could not find the specified profile.

The user is removed from the list of users in the UI but is still in the DB, users_entity table.