The blood from the war had not yet coagulated during Reconstruction, and President Johnson was of little to no help in guiding such healing forward. Indeed, many historians agree that Lincoln's notion of "malice towards none, charity for all" fell on rather deaf ears in many ways with the Johnson Administration during the infancy of Reconstruction.
Combine this tepid stewardship of Johnson's with a still smoldering South, and a distrustful, uncertain North, and I think you have an environment that is simply not ready for an organization dedicated to the "advancement of colored people."
Not that the concept of organized blacks for political influence was without precedent. The Abolitionist movement naturally comes to mind. But with the conclusion of the war, and the ratification of the 13th Amendment officially doing away with slavery, race relations in the nation were certainly at a bit of a crossroads as America caught it's breath in the war's wake, where any number of things could have happened. In our world, racial barriers, without the institution of slavery, began to crystallize, and they are not exactly melted even to this day down South.
But let us say, as you propose, a large, successful, post-war and post slavery movement of recently freed blacks did manage to bring about the NAACP in some form around, say, 1867.
With the actual enslavement of blacks made illegal, and the previously mentioned Johnson malaise, blatant racism in the South was left to fester, and to at least bubble up from time to time in the North. For let us not forget that even a fair portion of Abolitionists did not conclude that the black man was generally equal in faculties to the white man. (Lincoln himself had said he was uncertain if the two races could ever live in perfect harmony, or be exact equals.) I therefore contend that in such an atmosphere, a National Association for the Advancement of Colored People would be seen by many, if not most whites at the time, as a potentially threatening organization. Certainly in the racist South.
Those who previously had supported liberation of the blacks I think would feel apprehensive towards such an established order among them. A fear of organized revenge on the part of the unified black front would scare many whites, while others would be insulted at the notion of "uppity Negroes" trying to be too white.
The result? A war weary nation seeing the black Americans as asking for too much, too soon. Accusing them at best of not being satisfied, and at worst of trying to eliminate white America. This environment I feel would unify whole new demographics of people that may not have been unified before. It would certainly have accelerated the rebuilding of morale in the South among racist whites. The Mourners of the deceased Confederacy would be whipped up into a frenzy by such an organization.
This would lead, I feel in ultimate answer to you supposition, to increased violence among the races, and certainly legislation and government action to control, if not suppress the actions of the new union of blacks. Court injunctions may have been filed. Armed conflict despite the end of the war, even.
In short, Reconstruction was just too soon to assert such a position and mission.
The racism and foulness of the American South certainly was still present in 1909. In some ways even worse than before the war, given the atmosphere of defeat and judgment in which it would be allowed to stew for 50 years after the surrender. But, things up north, and other events throughout the country and world had at least to some extent allowed the nation to have scarred over from the war itself...and with that scar tissue came a certain degree of social toughness that allowed such an organization as the NAACP to come into being. Not a healing of the rifts, which of course we still struggle with...but a nation that provided just barely enough political cover for such an idea to have it's origins, when right after the war, it would not.
I do not think establishing, or attempting to establish the National Association for the Advancement of Colored People during Reconstruction, (as it existed in our time line) would have led to earlier advances of civil right for blacks, and indeed I postulate that such an eventuality may have actually delayed them.