Using triggers to add new user to a mailing list
I am not sure about how you've configured your environment but have you looked into this module? It appears to extend the rules a little bit.

https://www.drupal.org/project/user_mailman_register