Did you try Radio Shack? I remember going to a Radio Shack once since I needed an audio cable for my then-new DVD player and I knew they sold the gold-plated ones, and I saw a few Nintendo connectors there while searching racks upon racks of cables, including one for S-Video (the big fat circular one). If not there, maybe Circuit City or some place like that?
Radio Shack would be my first choice. They have too many different cables--finding the ones for my DVD player was tough enough! (My DVD player also has that red-green-blue triple headed connector). I know both the triple-headed one and S-Video are supposed to be better than the regular yellow jack. And if Radio Shack doesn't have it, aren't you able to custom order stuff there through the catalog?
I guess as a last resort you could look on e-Bay or something, I'd just be wary of return policies on stuff--make sure you get one that's got a warranty/return policy.