This is an interesting question, and a complicated one.
Why Neanderthals Died Off
First off, let's examine some of the reasons why experts believe neanderthals died off:
This species had incredible muscle mass, and matured earlier than us. Physically, they were much stronger than to us - a neanderthal in his prime may have been able to rip an arm off of a homo sapiens and beat him to death with it.
However, their great strength was also their biggest weakness: they could not scavenge the supplies needed to keep themselves, let alone their pregnant women, and children alive.
Basically, it is believed that they starved to death - as a species. They were also competing with homo sapiens, who required less food, and were, apparently, just a little bit smarter when it came to using tools and adapting to new situations.
Meeting Each Other
Our ancestors clearly spread throughout the entire world. These tribes traveled, by foot, across continent and oceans (over ice bridges, etc.). However, with the world frozen over to a large degree, the routes they would have followed are relatively limited. These species would have met sooner rather than later.
Being tribal in nature, and basically savages, there's only two ways their encounter could go: war, or inter-breeding.
Either way, fast forward a thousand years, and you're left with pretty much a single species.
Your Specific Question
But let's say that some Neanderthals did not starve out, and met up with homo sapiens only a few thousand years later. Would they both posses similar levels of technology? It's unlikely - look at Europeans vs Native Americans. That would give one side an advantage.
Genocide
If the species can't interbreed, then they are simply competitors for the same resources. Until very recently genocide was a very acceptable answer to dealing with your competition (native Americans, anyone? What about the Mayans, or the Conquistadors? When other people have stuff we want, we've killed them off mercilessly, and we're the same species).
One species would kill the other off, with my money being placed on homo sapiens - our ancestors were simply smarter.
Possible Cohabitation?
In my opinion this is highly unlikely, but here goes.
The cultural, and technological level of each race will matter immensely in this situation. The more barbaric, the less chance of them getting along.
For the two species to co-exist (which I am defining as one species not actively trying to stomp the other one out of existence) a few key conditions would have to be met:
1. Territories don't overlap
If one group is pushing into the other group's territory looking for resources then they're bound to come to blows. This has been the most basic reason human beings have killed each other ever since we first climbed out of trees.
2. Language & Culture
If both groups have advanced to the point where they have a decently developed language then they are more likely to try and communicate.
3. Development Level
If at least one group has outgrown the hunter-gatherer stage then that might work in favor of cohabitation. Evolving communities probably means that the foundation for trading has been established, not just killing strangers on sight.
4. A Common Foe
This is very likely the only true way for Neanderthals and homo sapiens to end up allied in some way. Neanderthals are stronger than homo sapiens, while homo sapiens are craftier. If they face a danger which threatens both, then they may team up, as long as communication is possible.
Imagine a group of Neanderthals meeting a raged group of battle weary HS. Instead of killing one another on sight, the HS trade some tools for food. Intrigues by these fur clad, mysterious strangers the Neanderthals don't just kill them, but offer them shelter, etc.
What you have to do is imagine a scenario where the two groups have something to offer each other, such as the brawny Neanderthals helping the clever HS hunt some dangerous creatures, or the two groups helping each other survive some cataclysm. That's what bonds two radically different communities together. In the aftermath of these two communities getting along and forming one united front others may follow in their path.