I know this sometimes が can be replaced with の, and as far as I know this happens when a noun is modifying a noun. Is this all there is to it? Is it important to always replace が or is it optional? Can it always be done?
As bertoni says, I think the situation you're referring to is when an entire phrase modifies a noun, and the subject of that phrase is marked with の instead of が.
I think it's mostly a matter of preference and either is acceptable.
In classical Japanese, が and の both had pretty much the same function (が was also used for possessives) and that may have something to do with it. One other theory I've always held, though I don't know if there's any truth to it, is that the subordinate clauses could be broken down two ways and the の conveys that everything after the の is something that "belongs" to the thing before the の:
I read before that の puts the emphasis on what follows it, whereas が puts the focus on the subject like it usually does. I suppose in this way it has similarities with the difference between は／が, but it doesn't seem to be anything like as strict.
Sometimes using のsounds quite natural to me because it almost sounds like possessive の, e.g. 彼の言うこと. 彼が言うこと still has 18-million hits on Google though, so I don't think this is anything to worry about too much, as long as you're able to understand it.