There isn't any direct reference for the birth date of Gautama Buddha in the Puranas. The notion of Gautama Buddha being born before 2000 BC comes from the chronology of dynasties of Indian kings given in the Puranas and Itihasas.
For instance, the first chapter of the twelfth canto of the Srimad Bhagavata Mahapurana is once instance in the Puranas where we get the entire chronology of dynasties in India during Kali Yuga. I'm not posting the entire chronology here since it'll be too long (but I do recommend to read the entire chapter, especially if you're a lover of Indian History). One iconic king of ancient India mentioned in the chapter is Ajatashatru:
vidhisāraḥ sutas tasyā-jātaśatrur bhaviṣyati darbhakas tat-suto bhāvī darbhakasyājayaḥ smṛtaḥ
The son of Kṣetrajña will be Vidhisāra, and his son will be Ajātaśatru. Ajātaśatru will have a son named Darbhaka, and his son will be Ajaya. (Srimad Bhagavata Mahapuranam 12.1.5)
For those who don't know about Ajatashatru, he was a king of the Haryanka dynasty (the Bhagavatam takes him as a member of the succeeding Shishunaga dynasty) in Magadha in Eastern India and is also described as an important contemporary of Gautama Buddha. Modern scholarship places his birthdate around early fourth century BCE. However, if we take 3102 BCE as the start of Kali-Yuga and trust the reliability of the chronology given in the Bhagavatam, his birthdate would be much earlier. According to Buddhist records, Gautama Buddha was 72 at the time of Ajatashatru's coronation. Therefore, according to the Bhagavatam, Gautama Buddha would be around the time 1887-1807 BCE.
A simple summary of the Bhagavatam's chronology is given below:
3228 BCE – Descension of Krishna
3138 BCE – The Mahabharata War; start of Brihadrath dynasty of Magadha;
start of Yudhisthir dynasty of Hastinapur
3102 BCE – Ascension of Krishna; start of Kali Yuga
2139 BCE – End of Brihadrath dynasty
2139–2001 BCE – Pradyota dynasty
2001–1641 BCE – Shishunaga dynasty
1887–1807 BCE – Gautama Buddha
1641–1541 BCE – Nandas
1541–1241 BCE – Maurya dynasty
1541–1507 BCE – Chandragupta Maurya
1507–1479 BCE – Bindusara
1479–1443 BCE – Ashokvardhan
1241–784 BCE – Shunga and Kanva dynasty
784–328 BCE – Andhra dynasty
328–83 BCE – Gupta dynasty
328–321 BCE – Chandragupta Vijayaditya
326 BCE – Alexander's invasion
321–270 BCE – Ashoka
102 BCE – CE 15 – Vikramāditya, established Vikram era in 57 BC
More details of the derivation of this chronology can be found here.