I won't go into the doctrinal disputes to which these ambiguities gave rise. The interested reader should consult the "Easter" entry in a good encyclopedia of theology (e.g., the Dictionnaire de Théologie Catholique). The generally favored solution was that Easter should always be on a Sunday, and that there should be some rule for determining a time fairly close to Passover. Just what this rule should be took a long time to hammer out. Relying upon the Jewish definition of Passover was uncongenial to many Christians, and as the Jewish calendar was not yet fixed by rule there was also the practical problem of waiting for the determination of the Sanhedrin in Jerusalem for a date which then had to be transmitted to widely separated churches throughout the Roman empire. To calculate Easter, then, Christians needed to find a lunar month in spring, which required both a definition exactly when spring began and a method of computing lunar months (i.e., a lunar calendar) that could be converted into the Julian calendar.
The rule eventually agreed upon was that Easter should be celebrated on the Sunday after the 14th day of the "Paschal" month. That Paschal, or Easter, month (essentially a Christian version of Nisan) is the one where the 14th day is on or next after the vernal equinox.
Even after this definition was generally accepted, there were still problems. When, exactly is the vernal equinox, and what sort of lunar calendar does one keep to track the Paschal month?
The Romans took the vernal equinox to be on March 25, a traditional date, to which they clung stubbornly for many years. Many of the eastern churches, however, took March 21 as the equinox. This measurement was fixed by direct observation of astronomers in Alexandria in the early third century. During that time, Alexandria was famous as a center of astronomic knowledge, and it was a natural place to go for expert consultation.
The lunar calendar used to track the new moons was also a subject of debate. The earliest surviving Easter tables show that the approximation 8 years = 99 months was used. This approximation results in an error of 1 day every 5.2 years. Clearly, for any long-term calculation of the moon, this rule will very quickly accumulate significant errors. In the early third century, a Roman named Augustalis introduced a new approximation: 84 years = 1039 months. This equation leads to an error of 1 day every 64.6 years—a significant improvement. Meanwhile the eastern churches, undoubtedly advised by Alexandrian astronomers, had found an even more accurate cycle: the familiar Metonic equation of 19 years = 235 months. This approximation has an error of only 1 day in 316.6 years.