It is highly unlikely that another species anatomically indistinguishable from H. sapiens but behaviorally similar to Neanderthals was supplanted worldwide in an extremely short span of time. Therefore, it seems appropriate to conclude that a latent capacity for symbolic reasoning was present when anatomically modern H. sapiens emerged and that our forebears discovered their radically new behavioral abilities somewhat later in time.
One of the most important means by which innovations are preserved and transmitted is language. Neanderthals had language themselves. This was proven in 1983 when a Neanderthal hyoid bone was found at the Kebara Cave in Israel. The hyoid is a small bone that holds the root of the tongue in place, a requirement to human speech and, therefore, its presence seems to imply some ability to speak.