"We need a man."
This is Genitive here, your version was in Accusative. I've seen a lot of natives making this mistake and using Accusative after "potrzebować" - still, a mistake.
When we're learning cases of our language, we do it with usage of a verb that works with this case and questions. For Accusative it's usually: "widzę (kogo? co?)" = I see (whom? what?)
Therefore "mężczyznę" would work for example as "Widzę mężczyznę" = I see a man.