If they had chosen "Reds", those concerned with the issue would still consider it essentially the same as Redmen. Redbirds is a terrible nickname, but it's tough to get angry about a bird, and it means the Martlets will have essentially the same nickname as the men.
What's interesting about the history of the nickname "Redmen" is that it was originally adopted by three separate universities (McGill, RMC, St John's) because their athletes wore red.
It doesn't take Sherlock Holmes to figure out that the nickname was associated with RMC Cadets wearing Scarlet Red as their dress uniform. RMC dropped Redmen (over a two-year period from 1995-1997) NOT because it was deemed racist (it clearly wasn't), but because it was not bilingual. Cadets had a vote: the final three options were Paladins, Phoenix, and Sabres. Thank heaven Paladins won the vote.
McGill and St John's started using some Native American imagery over time (mascots, logos), which turned it from an innocent nickname to a racist one. McGill dropped all of its Native imagery sometime in the 1980s, I believe, but it's tough to argue the nickname was innocent when the Redmen logo included the head of a Native American warrior in full headdress.