I'm unclear on exactly what you're asking.
First of all, by "paternal line cousins", do you mean all the descendants of your ancestors on your paternal line, or do you just mean the descendants along the male line? In other words, are you just looking for blood relatives named "Angus", or are you looking for ALL your Angus 1st, 2nd, 3rd cousins, etc.?
When you say you did your "DNA" with FTDNA, I guess you mean auDNA. Are you saying you did the auDNA test on Ancestry.com, too? When you say it was "easy" to identify cousins on Ancestry, do you mean DNA matches to these "paternal line cousins"?
Sometimes you don't get matches on one side of your family simply because it's a small family where nobody has tested (like I have on my maternal grandmother's father's side), but it sounds like you might also want to watch out for something that we euphemistically call a "NPE" - which refers to when biological daddy isn't who he's supposed to be, somewhere up the line.
I'm working with a guy right now who I determined has to be a second cousin of my wife's. He doesn't know anything about his paternal grandfather, because he left when the dad was small. The only thing that makes the various DNA results make sense, is if his biological grandfather was really my wife's great-uncle, who lived in the right place at the right time, instead. It was a bad family situation. This guy had no idea that might be going on - that his YDNA would, according to my calculations, match him with men with a completely unexpected surname.
You can only match one YDNA test taker with another, but those test takers have relatives, so maybe that's what you mean when you're looking to find cousins who haven't taken that test through YDNA?