Catelyn Stark: While Catelyn Stark is participating in a challenge, your opponents cannot trigger card abilities.

Rules Reference Guide: A duplicate grants its controller the following triggered game ability: “Interrupt: When the overlapping unique card would leave play, discard this duplicate to save that card. (Cannot be canceled.)”

Assuming Catelyn gained a Military icon somehow (Syrio's Training for example), would she prevent her opponent from triggering the duplicate save?

I'm assuming not, since the rules state the duplicate is a "triggered game ability" and Catelyn prevents "triggered card abilities", but the duplicate IS a card in the end, so I'm not 100% sure.

You hit the nail on the head: it's a game ability, which is specifically separate from a card ability. It's something the card's controller is doing, not the card itself is doing.