I have rebuilt trophies cache as suggested here and also the user cache and I run the cron entry manually.
- Promotion is active.
- Add to user group foo.
- User Groups -> User is NOT a member of these groups: Administrators
- User Profile and Options -> User is the following gender: Male
Update: it has applied to some users , but not to all of them.
Problem solved, thanks.