I was able to add taxonomy terms to my deployment plan by creating a Rule that gets triggered when a taxonomy term is saved, updated or deleted.

Save and Update actions work just fine -the term is added to the deployment plan-, BUT after successfully deleting a taxonomy term, and going back to the deployment plan page (admin/structure/deploy), it throws the following error:

EntityMalformedException: Missing bundle property on entity of type taxonomy_term. in entity_extract_ids() (line 7836 of /var/www/drupal7/includes/common.inc).

TEMP SOLUTION:
This apparently happens because deleting a taxonomy term does not have any effect on the records created by deploy module when adding records to its tables.

Finding the term deploy record on the deploy_manager_entities table and deleting it, fix the problem.