The good news is that these problems are going to diminish substantially pretty soon.
Recall the Orthodox calendar, which is 13 days off from the Western calendar. The Orthodox calendar is getting more and more off, by about 3 days every 400 years. But some of the Eastern Orthodox churches have adopted the Revised Julian calendar, also called the Milankovic calendar. The Revised Julian calendar omits 7 century leap years every 900 years, so there are 218 leap years instead of 225 every 900 years. (The two centuries that remain leap years are those that are equal to 200 or 600 mod 900, i.e., 2000, 2400, 2900, 3300, etc.) This makes an average year length of 365.24222 days. By contrast, the Gregorian calendar omits 3 century leap years every 400 years, so there are 97 leap years instead of 100 every 400 years. This makes an average year length of 365.2425; the two calendars will thus diverge by one day every 3600 years, on average. The true tropical year length is 365.24219, so the Revised Julian calendar is even a bit more accurate than our Gregorian one.
As I said earlier, it’s one thing to come up with a more accurate system; it’s another thing to get people to incur the transition costs. The Wikipedia article says that, so far, the Revised Julian calendar “has been adopted by the Orthodox churches of Constantinople, Alexandria, Antioch, Greece, Cyprus, Romania, Poland, and Bulgaria (the last in 1963), called the New calendarists. It has not been adopted by the Orthodox churches of Jerusalem, Russia, Serbia (including the uncanonical Macedonian Orthodox Church), Georgia, Mount Athos and the Greek Old Calendarists.” So there are basically three calendrical traditions out there: the Western Christian one (Gregorian), the traditional Orthodox one that’s in force in Russia (Julian), and the new Orthodox one that’s in force in Greece (Revised Julian), and there hasn’t seemed to be much movement toward convergence.
But it now looks as though more has been taking place behind the scenes than it seemed at first. John Paul II’s pontificate was marked by a rapprochement between Catholicism and Orthodox Christianity; for instance, the Pope apologized for the sack of Constantinople in 1204. Of course the Pope would have wanted the Orthodox to return to communion with Rome; that still doesn’t look like it’s going to happen, though individual Eastern churches, the so-called Eastern Catholics, have done so over the years: these include, for instance, the Armenian Catholic Church, the Melkite Greek-Catholic Church, and so on. But one area where there seems to be convergence is on the issue of calendars.
Seeing Catholics go back to the Julian calendar would be unthinkable — the Catholics invented the Gregorian calendar, after all, and it’s the Julian calendar that’s accumulating inaccuracy, so there’s no positive reason for adopting it. And seeing Julians go to the Gregorian calendar is unrealistic, because of the conservatism of Orthodox churches generally and the whiff of longstanding East-West animosity. On the other hand, the Revised Julian calendar has been a middle ground, culturally acceptable and at the same time astronomically more accurate.
So it was slightly surprising but not totally unexpected to see the new Pope issue, a bit in advance of Easter, the encyclical Quia pro unione, announcing the Vatican’s intention to switch to the Revised Julian system. This was already in the works under Benedict XVI, but the Vatican decided to wait for a new Pope just to reassure the other parties that the decision wouldn’t soon be reversed. (The buzz is that this decision came from Benedict XVI himself, who may have already decided at the time that he was on his way out.) At the same time, Patriarch Kirill of Moscow announced that the Russian church would likewise transition over. Both parties also announced their intention, in principle, to implement the command of the Council of Nicaea that all Christians celebrate Easter on the same day, but the details of that have yet to be hammered out. (I foresee either an adoption of the Dionysian tables or an actual reliance on lunar observation and computer-enhanced full-moon prediction.)
The Catholics won’t have to make any changes until 2800, which would be a leap year under the Gregorian calendar but not under the Revised Julian (which waits for 2900) — that’s almost 800 years. The Russians and others using the unreformed Julian calendar will make the 13-day jump “immediately” (in practice, it’ll probably be a few years, maybe up to a decade) but otherwise won’t have to change their practice until 2100. Until 2800, Catholics and Orthodox alike will be in synch with the secular systems, which all use the Gregorian calendar; after 2800, the difference will be one day for 100 years, then they’ll be in synch again for about 300 years, until 3200 — assuming the secular world doesn’t likewise change to Revised Julian.
What about Protestants? They’ll probably stay put, though perhaps the Anglican Communion will be next, and if that’s so, I would expect Lutherans to follow in the next century, and maybe everyone else within the next 800 years. Don’t count on the Jews to drop their lunisolar calendar anytime “soon,” though on the other hand, some prominent Reform and Conservative leaders have already put out feelers in that direction, citing as an advantage that Easter and Passover really ought to be synchronized.
UPDATE: Thanks to commenter arch1 for correcting 3100 to 3300.