Yes, Padmavati is the next birth of Vedavati.. Here is what Vishnu says in this excerpt from the Venkatachala Mahatmya of the Skanda Purana:
Formerly, in the auspicious Treta Yuga, I killed Ravana. At that time the girl Vedavati rendered assistance to Sri (Sita). Lakshmi appeared in the land of Janaka in the form of Sita. In the Panchavati forest, when I went away to kill Maricha, my younger brother followed me on being urged by Sita. In the meantime the king of Rakshasas came there to abduct Sita. Fire-god present in the (place of) Agnihotra sacrifice knew (i.e. anticipated) the attempt of Ravana. He took the real Sita to Patala and entrusted her to (his wife) Svaha. There was a splendid lady named Vedavati. Formerly, she was touched by the same Rakshasa (but not molested). Yet she cast off her body in fire. In order to kill Ravana she was created once again. It was she who was abducted by Ravana and kept in custody in Lanka. Afterwards when Ravana was killed, she entered fire once again. Agni handed over Lakshmi, my Janaki, who had been kept in protective custody by Svaha and told me about the attendant accompanying Sita: "O Lord, this is Vedavati who did what was pleasing to Sita. For the sake of Sita she remained in the abode of the Rakshasa as one imprisoned by him. Hence, delight her with a good boon along with Sri." On hearing these words of Fire-god, the splendid Sita told me: "O Lord, this Vedavati has always done what is pleasing to me. Hence she is a great devotee of the Lord. Hence, O Lord, choose her." I replied: "O goddess, I shall do so in the twenty-eighth Kali-yuga. Till then let her stay in the world of Brahma and be adored by Devas. Afterwards she will become the daughter of Earth and daughter of Viyat." Thus that beautiful lady had been formerly granted boons by me and Lakshmi. She is born of Earth in the city of Narayanapura. The chaste lady is on a par with Lakshmi. She has eyes like lotus. She has been granted boons by Padma.
In any case, I don't know of any scriptures that actually call Satyabhama an incarnation of Bhumidevi, although it's a very common belief. But Satyabhama being an incarnation of Bhumidevi wouldn't necessarily contradict Padmavati being the next birth of Vedavati. To be an incarnation of Bhumidevi is to have Bhumidevi as your soul. But different incarnations of Bhumidevi might have different subtle bodies, and it might be the case that Vedavati and Padmavati shared the same subtle body and Satyabhama could have had a different subtle body.