Updating taxonomy vocabularies with Rules?
Try the rules action "Set data value."  If the user includes a taxonomy reference field, you should be able to add or remove it this way.

Alternatives:
I'm not sure what you intend to use the vocabulary of usernames for, but it is straightforward to use the views module to generate a list of users by role.

Alternately, I have been using the flag module-- the latest Drupal 7 beta features rules integration-- to automatically flag users upon adding or removing roles.  You may be able to use flags instead of a vocabulary.