So what is the exact correspondence between the dates of the holidays of the two traditions?
The Chinese New Year is the beginning of the first month (农历正月) of the Chinese year, and as such has to fall on a new moon, or more precisely, "dark moon" - i.e. the day when moon is in front of the sun; this, incidentally, means that solar eclipses can only happen on the first or last day of a Chinese month, and lunar eclipses, only around the middle of a Chinese month). The idea of choosing the first month of the year is, basically, to do it so that the New Year Day is as close to the half-way point between the winter solstice (which in the traditional scheme of solar terms is viewed as the mid-winter point) and the spring equinox (which, in China is, notionally, the middle of the spring). In other words, the Chinese New Year day should be chosen as the new moon day closest to the first day of the lichun 立春 ("Start of spring") solar term (around Feb 4). Thus the Chinese New Year Day festivities are referred to as the Spring Festival (春节, chunjie). In other words, the Chinese New Year Day (the first day of the Chinese Year, or [农历]年初一 [Nongli] Nian Chuyi) has to be the first new moon on or after Jan 21.
In a similarly "lunisolar" way, the Easter is determined, more or less, as the sunday on or after the first full moon (the Paschal Moon) after the spring equinox. With some simplification, the Easter of the Catholic Church, and most other Western churches, happens on the first Sunday on or after the first full moon on or after March 22.
Since the full moon is always in the middle of the Chinese calendar month, we see that the Paschal Moon has to occur around the middle of the 2nd or 3rd month of the Chinese calendar (农历二月15日 or 农历三月15日). The former takes place in case of a "late New Year" (i.e., the Chinese New Year happens after the first day of Lichun), and the latter, if the Chinese New Year occurs early (before Lichun). The (Western) Easter would be celebrated, respectively, on the 1st Sunday after the middle of the 2nd or 3rd Lunar month.
Ash Wednesday, the first day of the Lent in the Western tradition, is 46 days before Easter. The last day before the Lent begins (the Shrove Tuesday, celebrated as Mardi Gras - the Fat Tuesday - in Latin Countries) is 47 days before Easter. Assuming 29 to 30 days in a lunar month, Mardi Gras should typically fall on the first Tuesday within the 7-day window that begins either 2-3 days before the Chinese New Year Day (in case of a "late New Year"), or 2-3 days before the end of the first month of the Chinese calendar (i.e. around 农历正月28日 - 农历二月5日) (in case of an "early New Year").
In other words, if the Chinese New Year Day comes during the Lichun term (on or after Feb 4), then the Mardi Gras will most likely fall on the Tuesday before or after the Chinese New Year Day. If the Chinese New Year Day occurs before Lichun (i.e., during the Xiaohan 小寒 term, before Feb 4), then Mardi Gras will be on a Tuesday a month after the Chinese New Year Day. Over a long period, both situations are approximately equally likely (since, by definition, Lichun is right in the middle of the period when the Chinese New Year Day may occur).
The Orthodox version
How will this work for those of the Eastern Orthodox persuasion? Both the Old Style and New Style Orthodox churches agree that Easter ought to be celebrated on the first Sunday on or after the first full moon (the [Orthodox] Paschal Moon) on or after March 22 of the Julian calendar - i.e. April 4 on the Gregorian calendar. Which means that in almost all years the Orthodox Easter (or Pascha - 巴斯克节 - as it is called in most Orthodox communities worldwide) has to occur on Sunday right around (or a few days after) the middle of the 3rd Lunar month (农历三月15日). The Orthodox equivalent of Mardi Gras is the "Butter Week" (Maslenitsa in Russian); this pre-Lent celebration ends on the Sunday 49 days before the Orthodox Easter, i.e. in most years, on the last Sunday of the first Lunar month or the first Sunday of the second Lunar Month.
In other words, the Maslenitsa Sunday and the Clean Monday are typically a month after the Chinese New Year, and 2 weeks after the Lantern Festival (元宵节 Yuan Xiao Jie). On rare occasions, when the Chinese New Year occurs very late (e.g., 2007-02-18, 2015-02-19), the full moon in the middle of the 2nd lunar month is late enough to be the [Orthodox] Paschal Moon; in these years the Butter Week happens right around the Chinese New Year. In the 22nd century the Julian calendar will fall back by one more day, so such situations will be even more rare.