The name Siddhartha occurs in the Pāli texts, in the form Siddhattha, only in the Jātakas and later commentarial works. It is not used in the Nikāyas or Vinaya as the name of the Buddha, though it is used for other people. The Jātakas are legendary material which we can't take seriously as historical accounts. Siddhartha is used in the Sanskrit Mahāvastu - technically a vinaya text of the Mahāsaṅghika sect but actually an extended and much elaborated biography, really a hagiography of the Buddha. The fact is that the more strictly biographical accounts of the Buddha, such as the Ariyapariyesanā Sutta, make no mention of his given name at all! The best we can say is that apart from the name Siddhartha there is no other name mentioned as a contender.
Gautama (P. Gotama) is something of a puzzle because it is a distinctively Brahmin name. There are several well known Brahmin philosophers called Gautama, and even a Brahminical Gautama Sūtra. Gautama is a traditional Brahmin gotra (P. gotta) name. The gotra is like a clan name, and indicates people descended from a particular ancestor. While the Vedic Brahmins did not worship their ancestors, whom they referred to as the pitaraḥ 'the fathers', they did revere them and in earlier versions of rebirth theories the good Brahmin would leave this world and go to the world of his fathers (women were not included in this scheme) for a time before coming back to this world. A hint into the original use of this term is that it also means a cow (go) shed (tra, 'protection') - the image is of the herd of cows enclosed and protected, similar to the relationship of the individual to the clan group. Only a few dozen traditional gotra names are recorded (there are lists in the pre-Buddhist Bṛhadāranyaka Upaniṣad for instance). Monier-Williams' Dictionary suggests there are 49, and gives Gautama as one of his examples in his Sanskrit dictionary.
It is mentioned many times through the Buddhist canon that the Buddha was a kṣatriya - that is of the class (varṇa)  which is associated with rulers and secular leadership - sometimes kṣatriya and rāja 'king, ruler' are treated as synonyms. The other three classes were priests (brāhmaṇa) merchants (vaiṣya) and peasants (śudra). Although the Buddha's father was referred to as a 'rāja' at that time the Śākya nation was more like an oligarchy or republic. Rāja cannot really mean king or royalty in this context, and probably just means 'leader' and even then one leader amongst many. In the commentarial traditions we find that the Śākyas did not follow Vedic, but Dravidian marriage customs, suggesting that perhaps they were not Āryans  at all (though this is a late tradition it must have had the ring of truth to survive since it contradicts his being a kṣatriya, which is a more convenient appellation in caste conscious India). There are pockets of Dravidian speaking peoples in North India still and it is usually assumed that they were the aboriginal inhabitants of the Ganges plain and were displaced by the encroaching Vedic/Sanskrit speaking peoples. There is some doubt about this theory now, and of course it tends to ignore the other major language group in India - Muṇḍa - traces of which can be found in the Ṛgveda (see my discussion of the Dhp 1 and 2 for an example of a Muṇḍa loan word in Sanskrit and Pāli). In any case politically and it seems socially the Śākyas were distinct from the Brahmins - making the fact of the Buddha's Brahmin surname even more odd.
There is evidence that Brahmins were not above adopting clans into the Āryan class/caste system - sometimes making their priests honorary Brahmins. It has been suggested that perhaps the Śākyans employed a Brahmin purohita (a priest) and adopted his gotra name. If this is true it shows how very powerful the influence of the Brahmins was on the culture of Greater Magadha even at this early stage when it was dominated by the various śramaṇa groups. The Vedic languages were a powerful means of cultural imperialism.
To summarise then: while there is no other contender the name Siddhartha is not associated with the Buddha in the earliest texts, though Gautama is. Gautama however is a distinctive traditional Brahmin name which does not fit the general picture of the Buddha's non-Brahmin, probably non-Āryan background.
Such uncertainty does not sit well with religious sentiments, and so the legends which filled the gaps in our knowledge gained the status of facts: the Buddha's name simply is Siddhartha Gautama and we 'know' many details of his parentage and life. Of course it is possible that the legend is based on a fact not recorded in the suttas, however unlikely this seems. Perhaps the Buddha deliberately obscured aspects of his pre-enlightenment existence. I've noticed that occasionally when people wish to belittle me they will insist on using my birth name instead of my Buddhist name - particularly when denying the validity of my ordination. Perhaps the Buddha wished to create a bit of distance between that old identity and 'the Tathāgata'. Other details of his life are equally vague, and even more elaborately filled in by Buddhists. Indeed the further we get from the actual life the more elaborate the stories become until they leave behind any sense of historicity.
Does it matter? I think not. The Buddha is a symbol of our potential - every human being if they pursue the dhamma can become 'like that' (tathāgata), i.e. we can all have that experience which the Buddha had. The fact is that people have been having that experience ever since the Buddha's first disciples and right down to the present. Buddhists do not rely on the divinity of the Buddha. We have the dhamma - the ways and means of following the Buddha. We have the Saṅgha - each other, but more especially those with experience, with the experience, to support and guide us. The main reason for pointing out the problems with the hagiographic narratives is to prevent us from deifying that version of the Buddha who is more a product of human imagination than of history. Such a figure must remain a symbol and not become an idol if we are to retain the spirit of the Buddha's teaching.
See also Some Additional Notes which looks again at the issue of the name Gautama.18.5.2011 Update:
The word śākyamuni is used in the Lalitavisatara and the Mahāvastu, two of the earliest Mahāyāna texts. It also occurs in the Aṣṭasāhasrikā Prajñāpāramitā [Sūtra] where several times we find the phrase:
śākyamunirnāma tathāgato 'rhan samyaksaṃbuddho vidyācaraṇasaṃpannaḥ sugato lokavid anuttaraḥ puruṣadamyasārathiḥ śāstā devānāṃ ca manuṣyānāṃ ca buddho bhagavāniti
More or less this same phrase is found in the Ajitasenavyākaraṇa which Williams discusses as a Mahāyāna sūtra that originally belonged to a pre-mahāyāna tradition (Mahāyāna Buddhism, p.26). The phrase śākyamuniṃ tathāgataṃ appears to occur only once in both the long and short Sukhāvatīvyūha Sūtras.
The tathāgata named Śākyamuni: the worthy, the fully and perfectly awoken, endowed with knowledge and conduct, in a good state, excelled in understanding the world, a trainer of people, a charioteer for gods and humans, awakened, fortunate.
However the name Śākyamuni appears not to occur at all in the Śālistambasūtram, nor in the Ratnaguṇasaṃcayagāthā (though 'śakya' does).
This is a brief and far from comprehensive survey of the Mahāyāna sūtras generally acknowledged to be early, and which can be found online and searched electronically. While not universal, nor always prominent, the name does seem to be established by the time these texts were composed - by perhaps the first century before the common era or a little before, but probably post Aśoka (to take him as a reference point).
- Class' better captures the higher level fourfold division of Indian society. 'Caste' is a translation of jāti 'birth' which is also used this way in Pāli - see e.g. the Pūraḷāsa Sutta in the Suttanipāta. Jāti often referred to one's specific occupation.
- 'Āryan' as a cultural description is falling out of favour because it is seen as politically incorrect. The people in question probably spoke a range of dialects all related very closely to Vedic or Sanskrit and to Iranian languages of the same period - I've seen it said for instance that Pāli is not descended directly from the Vedic of the Vedas, but from a near relative. Anyway I'm now uncertain how to refer to the people (if they were a people) or this family of languages. Vedic is not quite right, and Sanskrit has only limited applicability.