Turkish is interesting here. They have two words for "and" (ve and ile), but only ile means "with" and implies two things joined together. I believe that "adamla kadin nerede" is the same as "adam ile kadin nerede" as the suffix here is adam(-ile), which is abbreviated with vowel harmony to adam-la.
If the order is not important, why is "where are the woman and the man" considered wrong as a translation? Also "where is the woman with the man" is considered wrong, it does sound a little bit weird but i've seen weirder... It seemed to me that "adamla" means "with the man", that implies that the main subject is the woman and one of her characteristics is that she is with a man (as you would say "the woman with the red dress"), which is why i'd put her first in the sentence.
It is not accepted because it is not the order in this sentence. But it doesn't matter when you talk.
'A woman (who is) with a man' would be 'Adamla(/ın yanında) olan kadın'. 'Adam ile/ve kadın' means a man and a woman whereas 'adamla olan kadın' a woman who is together with a man.