If I wanted to describe the person I was speaking about as being Japanese, to me it seems natural to say:
日本人{にほんじん}の相手{あいて}
... however, one time a Japanese teacher told me it's more correct to say:
相手{あいて}の日本人{にほんじん}
... but that never sat right with me. To me the first way seems more logical because it goes from more general to more specific.
Is 相手{あいて}の日本人{にほんじん} more correct?
If so, why?
This の signifies the two words refer to the same thing, and 相手の日本人 means someone who is 相手 and 日本人 at the same time. I do not think that using 日本人の相手 when you mean 相手の日本人 is incorrect. However, 日本人の相手 is ambiguous: it may mean the same as 相手の日本人, but it may also mean an opponent/partner/company of some Japanese person, as in 吉田さんの相手. This is probably why the teacher said that it is more correct to say 相手の日本人 than to say 日本人の相手.
If you think that 日本人の相手 is more natural than 相手の日本人, that may be because 日本人の相手 corresponds better to the English expression, where “Japanese” is an adjective.
Tsuyoshi Ito's answer is right, but I think there is another factor here. It is specifity. 相手 'the other person' is specific enough to identify the person. Nevertheless, if you modify it as 日本人の相手, it sounds like there are several people that are referred to as 相手, and you are narrowing it down by adding 日本人の, which is redundant, and hence not appropriate, if there is only one person you are talking to. On the other hand 日本人 'Japanese person' is not specific enough, and it makes sense to modify it with 相手の, making it 相手の日本人.
Hmm, this may be a tough answer to argue against the two previous which are answered by native speakers. But here goes...
To me it just seems like a matter of perspective. With 日本人の相手, it's saying "Out of (the group of) Japanese people, the one who is an 相手." With 相手の日本人, it's "Out of all the 相手's, the one who is Japanese". So it seems like a choice of with what you want to associate the person more; are you placing more emphasis on them being an 相手 or a 日本人. However, for reasons I can't explain, it does sound like 日本人の相手 could be representing more than one person, whereas 相手の日本人 sounds like only one person.
I also stumbled upon something similar once. A friend of mine was saying "Enjoy the rest of your summer". She said it as 「残りの夏休みを過ごしてください」and it didn't sit well with me either (and still doesn't) -- I thought it should be 夏休みの残り. But it seems like the same perspective issue. "Of all the things that have a remainder, the one that is summer" vs. "Of all the parts of summer, the remaining part".
I think as English speakers, 日本人の相手 sounds more natural to us because in Japanese 101, we're taught to "adjectivize" nouns this way, like 日本の車, スイスの時計, ドイツのビール, and so on. So we project this same pattern onto people. The confusion is that with the previous examples, it makes no sense to switch the order. Take 日本の車: the two groups are Japan and cars, and there is no larger "semantic group" that contains both of them. The groups are so separate that only "a car from Japan" makes sense; "a Japan from cars" makes no sense. However, in the case of 相手 and 日本人, the two groups are part of the same larger "semantic group": people. So it confuses us about which one should modify the other one. But going back to our knowledge of "adjectivizing" nouns, we tend to put 日本人の as the adjective.
「どこの相手？」and narrowing it down my way answers the question 「日本人の何？」. Never thought of it this way.
相手の日本人 sounds strange to me/us, but OK for you. Maybe you're answering 「どのような日本人？ and that's OK, but I'm trying to answer 「相手の何？」 and that doesn't make sense.
My answer will undoubtedly not be as complete as Ito-san's, but here's my two cents:
Instead of looking at の as a possessive particle, you should try to see it as a particle attaching some quality or attribute to said noun. In that sense 相手の日本人 does not mean the 日本人 of 相手, but the 日本人 having an 相手 quality.
In the same sense 残りの夏休み (from istrasci's answer) means The part of the summer vacation that has the 'leftness' quality. Aka: the part that's left.
I am by no means an officially trained linguistic, but ever since I began looking at の in this way, it made my world a lot simpler. In fact, this is in my view also how the 'possessive の' works:
私の友達 → The friend having an 'of me' quality → my friend.
