Just following up on Carol's comment. Obviously her statements are correct. However, your question was "When are the employer match contributions subject to FICA taxes? Is it when distributed or when contributed to the plan? This plan has a 2/20 vesting schedule.". Since the employer contribution has a vesting schedule, it is not considered an annual deferral until the amount is vested. At that time the accumulated interest is also considered in determining the annual deferral. See section 1.457-2(b) of the regulations.
With respect to FICA treatment, the regulations mentioned in Carol's response governs the taxation. Once there is no substantial risk of forfeiture, the amounts are taxable for FICA purposes (to the extent the employees regular wages are taxable). You asked about whether the amounts are taxable when they are an annual deferral or when distributed. This presents an interesting questions. Under the special timing rule of 3121(v)(2)©, amounts are taxable when they are not subject to a substantial risk of forfeiture. This is the special timing rule for NQDC and is an exception to the general timing rule that amounts are taxable when paid or made available for FICA purposes. This apples to all NQDC. There is a special non-duplication rule contained in section 31.3121(v)(2)-1(d) that provides that if the amounts were properly reported as FICA wages under the special timing rule under 3121(v)(2)©, that the amounts are not considered FICA wages when distributed.
So if amounts were not reported properly as FICA wages when they were annual deferrals, the regulations would read that amounts are reported as FICA wages when the amounts are paid. This is the proper FICA tax treatment for all NQDC but when you are dealing with a governmental 457(b) plan there does appear to be an argument as to whether this applies. In discussions with the IRS general counsel's office on employment taxes they believe this does apply to governmental 457(b) plans. However, there appears to be a reporting disconnect as the requirement for all distributions from a governmental 457(b) is to report on a form 1099-R. The employer generally does not know when the distributions take place. The vendor does not know that FICA taxes have not been paid.
So like all NQDC, the important thing is to properly report the FICA wages as you go.