If you say someone is "a countryman of mine", you mean that he and you are 'fellows' as far as nationality is concerned. That is what I imagine TCL is now - and I was earlier - getting at. We both take the view that the one, as it were, subsumes the other and that using both is, therefore, unnecessary. (Or tautological...or even pleonastic...what the hey!)
Re dictionaries, here are parts of what two of the key ones say about tautology...
a) Chambers: "...use of words...that repeat something already implied..."
b)The Oxford English Dictionary: "...a repetition of...the same idea...in other words"
That is, we are dealing here with implications and ideas which are, by definition, fluid and different people might well see them in different lights.
The main thing is that Chambers seems quite happy to use the phrase 'fellow countryman' as pointed out earlier, so we might just as well leave it at that.