To my knowledge, scientific names, once bestowed, are immutable!
True, but this does not support your position. It's true that the original spelling Homo sapiens neanderthalensis won't be changed. This comes under the rule of immutable names. But (i) Neanderthal Man isn't a scientific name in that sense (a taxonomic name), protected by international convention; and (ii) the immutability applies only to that subspecies. If a reclassification occurs in the light of new knowledge, and it's decides that what was formerly called this now deserves to be a species in its own right, the new species gets a name of its own: as we have recently seen Homo heidelbergensis, H. antecessor and so on; this could be H. neandertalensis, H. neumannii, or whatever. It would be a new name.
They changed my "Brontosaurus" to "Apatosaurus"...
No they didn't. Scientific names are immutable. The Apatosaurus was described and named. Some years later a specimen was found that was described and named Brontosaurus; unfortunately it later turned out to be the same kind of animal as the existing Apatosaurus. So the old name has priority. The new name Brontosaurus caught on, but is invalid.
