Gregorian calendar as common reckoning? I can assure you that the Orthodox Church does not use the Papal reckoning for Easter. Likewise, you claim that people did not share a common calendar over those locales is quite false. The Roman civil calendar was known in all of those areas. “Date X” (Ides Aprilia, for example) could have been used. But it wasn’t. The problem is that local communities had locally chosen different ways to date the holiday. What had happened is that some communities used the Jewish (lunard) date, Nissan 15 to 22, while others picked a date in the spring on the Roman calendar (which is mostly solar). Thus, some communities were fasting while others were celebrating.
Now, the Jewish calendar was not well known in the Empire. The civil calendar was, and it was at least theoretically synchronized with the solstices. Therefore, the Council of Nicea determined that, for the sake of everybody playing the same note at the same time, the “method of Alexandria” would be used. This method was essentially the first Sunday after the first full moon after the Vernal Equinox, a compromise between purely lunar and solar methods.
However, it should be noted that this equinox was not determined for the whole Church by means of astronomical observation. Instead, an “ecclesiastic” equinox was chosen that corresponded to the equinox of that time. Likewise, it is an “ecclesiastic” full moon that is used, not an observed full moon. This was probably to allow for calendars to be planned ahead of time.
The minutes and canons of the First Ecumenical Council (Nicea) get into more detail on this.
Now, there is one little sticking point regarding the Christian Passover and the Jewish Passover. One of the Nicean Canons stated that the Christian holiday was not to be celebrated “with the Jews”. Unfortunately, this was not explicitly elaborated. One interpretation is that the Christian feast is not to be celebrated in the synagogues. At the time, some Christian communities still held their worship in synagogues. Another interpretation was that it was not to coincide at all with the Jewish celebration.
While modern authors, resplendent in their comfort and safety, like to claim that “antisemitism” was the cause, at the time, Christians were persecuted by Jews. It was the Jews who had the political connections and power to bring the state down on the Christians, especially after the Jewish communities formally cast out the “Nazarites”. No longer considered Jews, they no longer had the religious exemption granted Jews.
Unfortunately, instead of responding as we were supposed to, once the tables were turned, we Christians abused power as badly and worse as it was abused against us.
Now, even though the Nicene Council (AD 325) did determine a standard date for the celebration, this still took some time to get all the way around. As late as AD664 there were communities in the British Isles who celebrated according to a method variant from the standard simplification–although they did not use the quartedecimian determination, no matter what Bede might have claimed.
Finally, just to complicate matters further, the West does not use the same calendar as the Ancient Church. The Ancient Church used the Julian calendar, which is longer than the actual tropical year. A few smarty guys in Rome did a dramatic demonstration of the severity of equinoctal precession for a horrified Pope Gregory, who commanded a calendrical revision in the 16th century.
England did not adopt the calendar until the 18th century, and Russia took even longer. Even in that case, most Orthodox countries only adopted it as a civil calendar. So the Orthodox use the Julian calendar to determine the date (except for in Finland). However, the Orthodox Church also tends to interpret “with the Jews” to mean “coincide at all”, so there is an additional complication added that if the Orthodox calculation gives a date that is before or upon Jewish Passover, the holiday is delayed to the NEXT Sunday after the NEXT full moon.