It is not easy to explain why such constructions are idiomatic
It is fairly easy to explain. Back when case meant something in English, when we had nominative, dative, accusative and genitive, prepositions governed cases. Some took more than one case depending on the specific meaning. Thus in took the dative if it was expressing motion into something and accusative if expressed location in something.
Nowdays, we have lost much of the notion of case. We have, at best, three cases, subjective, objective and possessive, and then only in pronouns. This is why reverting to pronouns can be helpful in resolving these questions, as Wordwind pointed out so ably. In the case of nouns we have only two cases that we can determine from the form of the word, let's call them common and possessive. This being the case we have lost the feeling for prepositions taking certain cases. It's only those that take the possessive that we notice and of is maybe the only one that takes the possessive, and, as the portrait of the king('s) in Bingley's link shows us, it doesn't always take the possessive.
