The Oxford English Dictionary has: "Apparently coined by two U.S. transport engineers, Roy Cottam and Sam Schwartz ('Gridlock Sam'), working for the New York Traffic Department, The term was popularized during a strike by city workers in early 1980. 'One day, Roy spoke of his fears if we closed the streets in the Theater District, the grid system would "lock-up" and all traffic would grind to a halt. Soon we simply juxtaposed the word, and the term gridlock was born' (Sam Schwartz, 2001)."
However, in William Safire's column on April 27, 1980, "Gridlock Sam" (who now writes for the New York Daily News) admitted that the term had been used by the department as far back as 1971, so he didn't coin it. I tried to look for the word in the Municipal Archives, but with no luck.
3 April 1980, New York Times, pg. B2:
At times, the volume threatened to approach the dread condition traffic engineers call "grid lock," which means there are so many cars trying to move in all directions that it become impossible to move.
6 April 1980, New York Times, pg. E16:
Consider grid lock from the vocabulary of traffic engineers. It refers to what happens when so many cars converge in too few streets that they become literally immobilized.
27 April 1980, New York Times, p. SM5:
According to Samuel I. Schwartz, assistant commissioner of the city's Department of Transportation, he first heard the term used around the office in 1971, when an ambitious "Red Zone" banning all autos was being planned: "We were worried that iit might overload the connecting streets and the grid would lock, so we talked about a 'gridlock.' Then, in 1980, we put it in the transit-strike contingency plan, and all of a sudden it was all over the papers."