It's not really a counter example. The Eurocrats would love the peoples of Europe to be citizens of a united states of Europe (polls suggest people are not so inclined). The Schengen agreement is a logical step towards that goal and is undeniably helpful for travellers. Countries in the continent of America don't appear to have any such ambition.
Wouldn't the "United" states be similar? Each "state" of the union was like it's own country until they formed their own group. People from the USA usually identify with their state first before the country.