I have always heard that on the first night of Shavuos you should wait till Tzais HaKochavim for Maariv in order to have Temimos - 7 complete weeks of Sefira. Recently I heard that Harav Ovadia Yosef holds that it is not an issue and you may make an early Yom Tov. Does anyone know if this is correct and what the reasoning is?
See this article (Hebrew pdf) arguing for the "need not wait" position.
The Rishonim and Shulchan Aruch never said to wait; when Shulchan Aruch describes the order of prayers for Shavuos, it doesn't say anything about waiting. The note to wait appeared later (and appears in Be'er Heitev OC 494 as "the Achronim have written"), and was not agreed upon by all. While the "wait" practice has become very common today, it wouldn't at all surprise me if Rav Yosef is following the "need not wait" opinion.
A similar question comes up with regards to davening early on the first night of Shmini Atzeres (but you're ending Sukkos early!), on which the Taz (OC 668) says it's fine: Hashem said keep 7 days of Sukkos and Hashem said keep Shmini Atzeres afterwards, and Hashem said "you should start all yomtovs a bit early", so clearly Hashem is okay with us starting Shmini Atzeres early.
Harav Dovid Zvi Hoffmann in his She'eilos u'Teshuvos Melamed Leho'il (108) permits even Kiddush bein hashemoshos in countries where Nacht is very late.