Note that they could both be represented as мэн in Cyrillic -- there's really no way of representing the vowel difference in the standard Russian alphabet. (Just as the English version of the Latin alphabet has no satisfactory way to represent the sound of ы.)
It doesn't matter: we used the IPA ([mæn] - man, [men] - men), I don't know why Americans don't use it.
And I remember from my first year Russian class that a LOT of English speakers had huge difficulty (at first) hearing and pronouncing the difference between ы and the diphthong ой. (So a lot of people pronounced мы, ты, вы... like мой, той, вой...)
Did they really hear like that?
True, the sparrow probably wasn't a very good example -- I doubt any ESL teacher would include "sparrow" on a vocabulary list for students below the advanced level. (Whereas words like "chicken", "pigeon", and "parrot" might be introduced even in a beginning class, although after the generic term "bird".)
Your requirements for fluency are too strict.