In the 1970s, using human and chimpanzee models, the larynx of a neanderthal fossil was reconstructed leading the researchers involved in the study to conclude that neanderthal was incapable of human speech. This reconstruction was disputed based on the placement of they hyoid bone (which was unlike the position in newborn or adult humans, stillborn chimpanzees or adult chimpanzees and positioned on the basis of ability to swallow) and whether neanderthal man could speak remained uncertain.
In 1989, new neanderthal fossil evidence - a well preserved hyoid bone identical in size and shape to modern humans - indicated that indeed at least the skeletal structures and morphology necessary for speech were present at this stage in human evolution, and has changed little in the past 60 000 years. Of course, this alone doesn't prove that Neanderthal man was capable of speech, but along with other evidence - adequate brain development, and social organization that would necessitate some form of higher communication - certainly suggests that this was the case.
More recent computer simulations based on models of neanderthal vocal tracts demonstrated that if the larynx was posistioned like that of humans, the voice would have been extremely low and difficult to communicate effectively with. If it was positioned like that of a chimp, the words would be "slushy and difficult to understand."
The problem with any model of the vocal tract is that the ability to speak is dependent on the larynx, tongue and other soft tissues that don't fossilize well so their size and position in neanderthal man is speculative at best, but with evidence both for and against neanderthal speech a consensus in this debate is unlikely to be settled soon.
On the other hand, there may be a genetic answer to the neanderthal speech question: FoxP2. This highly conserved gene is required for some of the developments necessary for speech and tracing it's evolution could give answers as to when language developed.