I live in New York state in the U.S., and it's most common to hear people say "change of plan" (singular). Sometimes I do hear "change of plans" (plural), but it's much less common, and it does sound a little weird to me. Both work technically, though: You can think of it as one all-encompassing plan, or you think of it as lots of little plans that get grouped together. But as others have said, both forms are fixed expressions, and both are correct.