When's the earliest time one can make an Eiruv Tavshilin on erev yom tov?
With regards to the earliest you can make the Eruv on Erev Yom Tov (your actual question), The Nitei Gavriel (Laws of Yom Tov II 81:10) says you can even make it the whole day, even in the morning (meaning not the night before). In the footnotes he explains none of the earlier authorities address this issue, but it appears that it is better to wait till morning. See there for more sources and information.
If you did do it earlier than Erev Yom Tov, he quotes The Shulchan Aruch Harav (527:2) as having said you've fulfilled your obligation (Bedi'eved), but should do it again without a blessing.
A little more depth:
In the Shulchan Aruch Harav (527:2), he brings practical halachic differences between the two reasons. If you want to impress on people the importance of Yom Tov, you could make the Eruv Tavshillin weeks in advance (assuming the cooked food will survive), and one Eruv could be made for many Yomim Tovim.
If however, you want to impress on people the importance of Shabbat, you must make the Eruv only on right before the holiday, and only for that holiday. Otherwise, you won't be remembering the importance of Shabbat.
Therefore, you should really only make the Eruv before Yom Tov, and only for that Yom Tov.
If you did make an Eruv a while before (intending it to cover this Yom Tov), and you forgot to make another Eruv before the Chag, you've can rely on the first Eruv you made. However, if you remember before Yom Tov you should make a new Eruv or take the old Eruv and say "With this I will be able to cook...", but don't make the blessing.
Lchatchila the Eruv should be made on Erev Yom Tov - anytime starting from the night before (Orach Chaim 527:14). According to the Biur Halacha the food used in the eruv should preferably have been baked or cooked on Erev Yom Tov.
If it was made earlier - Lchatchila he should make another one without a Bracha on Erev Yom Tov (Orach Chaim 527:13). Bdieved it can be made earlier so long it is done with a food item that will last and it should be done without a Bracha and a Tenai (Minchas Aharon 1 Siman 145)
See that Kitzur Yalkut Yosef in סימן תקכז - הלכות עירובי תבשילין that one should do it during the 24 hours of Erev Yom Tov.
If one does it earlier, one should redo it - but without a Bracha. However if one did not redo it, it is still valid.
He goes so far as to say one can use the Erev Tavshilin of Rosh Hashana for Sukkoth, if one had that intention; though it's not a recommended practice.