Hmm. The problems here are what you mean by 'ethnicity' and what degree of intention you want from the state. But here are some things that might be worth keeping in mind:
The majority of PNG 'tribes' are in fact language groups. The notion of a 'tribe' or ethnicity arose here (and in swathes of Africa and South America) out of the colonial habit of dividing people on the basis of language. In actual fact, social, political and trade linkages often occurred across language boundaries, and in some areas there was a lot of intermarriage. Bilingualism was common, even in areas where travel was difficult; in Australia - which had a less intrusive geography - even more so. Conversely, there could also be a lot of enmity within a linguistic group. Also, the distribution of cultural traits does not match lingusitic divisions all that clearly, or do so only at absurd levels: Austronesian-speaking peoples in PNG tend to have a certain kinship formation unlike Papuan speaker, but an "Austronesian" ethnicity is a bit far fetched even as a linguistic classification (!), and has no socio-political reality. Yet as time has progressed, language groups have tended to form themselves into relatively organized groups (ie. Relative to anarchy) more or less along colonial divisions. There have, for instance, been Papuan separatist movements Papua was colonized by Britain/Australia while New Guinea was colonized by Germany until 1914. From what I have read of the African and South American experience, the situation is broadly similar.
From an anthropological perspective, then, the only tenable answer here is that the notion of 'ethnicity' is not straightforward and has been everywhere modulated by the requirements of state.
Nowhere less so than in Europe. It is interesting that the anthropological concept of culture traces back to the German Romantics, specially Herder and the philologists, and there too we can find a substantial root of nationalism. Within the French tradition too, the concept of culture was developed together with that of a secular nationalism, but the decisive moment, as I see it, was the linkage of a people's character to language in the German stream. This had a very strong echo, even in Malinowski. It was the scholarly imprimatur to the colonial convenience of administration by language groups - born from the nationalist fiction of the Volk-character of European linguistic groups.
Thiago Cintra Oppermann