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 背が高い:
背が高い, 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
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
Now all you have to do is to combine the above two points:
Clumsy nonsense in English, idiomatic in Japanese.