Your reply is right regarding immigration, for citizenship is the country where you were born.the need for police record is determined by countries in which a person lived in the past 3 years.
So if one lived in Argentina for the last 3 years, then one does not need police record from any country other than Argentina.
Also if US citizen lived in, say, Paraguay for the last 3 years, then he does not need US police certificate at all. He needs police certificate from Paraguay.
This is not determined by passport. This is determined by countries of one's residence in the last 3 years.