The earliest time that one may recite the Sh'ma is Tzeis ha'Kochavim (nightfall). However, many communities in Chutz la'Aretz, who often have difficulties in gathering a Minyan again for Ma'ariv, Daven Ma'ariv any time after P'lag ha'Minchah. Those who do, should take care to repeat the Sh'ma again after nightfall. Bear in mind that this is 'Sha'as ha'Dechak' (only an emergency) and it is prefereble to Daven with a Minyan after nightfall if possible.

Those communities which do adopt this Minhag, should make a point of Davenning Minchah before P'lag, and what's more, they should do so regularly, since they have accepted the opinion of Rebbi Yehudah, in which case it is better not to chop and change from one day to the next.

Another alternative is for the community to Daven Minchah immediately after P'lag, and Ma'ariv after Sheki'ah (sunset).

Most of the above is based on the Mishnah Berurah 235:1.

Kindest regards

Eliezer Chrysler