The phrase 心の冷たい人 (which is given by Japanese-English dictionary on OS X) looks wrong to me, but given that it's an example in a respected dictionary and confirmed by tens of thousands of Google hits, I have to assume it's correct. It's a lot less clumsy than how I'd naïvely write it, 冷たい心がある人, but its word order still doesn't line up with anything else I've seen. Is this just an idiomatic saying that I should just accept as correct, or is this a pattern that shows up a lot?
This doesn't strike me as the slightest bit unusual. Relative phrases such as this are very common in Japanese. You can easily substitute similar phrases for 心が冷たい, such as 背が高い:
- あの人は背が高いです。 ("That person is tall.")
- 背が高い人 (lit. "A person who is tall"; "A tall person" [with the emphasis on 背])
- 背の高い人 (lit. "A person who is tall"; "A tall person" [with no particular emphasis])
背が高い, being a complete phrase, is perfectly legal as a modifier on a noun (although the が does often change to の depending on the emphasis).
The first point to note is that, to say "A's B is C", it is common to say "AはBがC", especially if B is an integral part of A. So to say "That person's heart is cold", you can say either of the below
あの人は心が冷たい → As for that person, (his/her) heart is cold.
あの人の心は冷たい → As for that person's heart, (it) is cold.
Both are correct, but the former is more idiomatic in Japanese, probably because it makes more sense to make the person the topic of the sentence than his/her heart.
The second point to note is that Japanese is both lenient and inexplicit about the grammatical role that the modified noun has in a relative clause.
To put some color on that, 書く物 can mean
- 物が書く → 書く物 something that writes (subject)
- 物を書く → 書く物 something that sby writes (object)
- 物で書く → 書く物 something that sby writes with (postpositional phrase)
- 物に書く → 書く物 something that sby writes on (postpositional phrase)
Now all you have to do is to combine the above two points:
- （あの）人は心が冷たい → 心の／が冷たい人 (topic)
- As for that guy, the heart is cold → A guy as for whom the heart is cold
Clumsy nonsense in English, idiomatic in Japanese.