Fix the position of one of the men, then there are 4! ways to arrange the other men. Now consider the position to the left of the first man, and place a woman there; there are 5 ways to do this. Then there are 4! ways to arrange the other women. So I get 4!*5*4!, which is the same as your answer.
I admit I have a hard time following your method, but it seems right.