What is the correspondence between combinatorial problems and the location of the zeroes of polynomials called?
Rota himself called this correspondence "the critical problem". You can find the full quote in Michael Lugo's blog.
As explained by Garrett Birkhoff (in his book on Lattice Theory), the critical problem consists in locating the zeros of the characteristic polynomial of a geometric lattice, as defined by the Möbius function. Many extremal combinatorial problems, notably the classical problem of graph-coloring, can be re-stated as critical problems.
Combinatorial Geometries is a classic reference.
Other combinatorially defined polynomials (with further references) can be found in Lugo's blog mentioned above.
As Carlo Beenakker said, Rota called this the "critical problem." Rota intentionally left the statement of the critical problem slightly vague. Perhaps the closest he came to a precise formulation was in his paper with Joseph P.S. Kung and M. Ram Murty, "On the Rédei zeta function," J. Number Theory 12 (1980), 421–436. The abstract of that paper reads:
Let L be a locally finite lattice. An order function ν on L is a function defined on pairs of elements x, y (with x ≤ y) in L such that ν(x, y) = ν(x, z) ν(z, y). The Rédei zeta function of L is given by ϱ(s; L) = Σx∈Lμ(Ô, x) ν(Ô, x)−s. It generalizes the following functions: the chromatic polynomial of a graph, the characteristic polynomial of a lattice, the inverse of the Dedekind zeta function of a number field, the inverse of the Weil zeta function for a variety over a finite field, Philip Hall's φ-function for a group and Rédei's zeta function for an abelian group. Moreover, the paradigmatic problem in all these areas can be stated in terms of the location of the zeroes of the Rédei zeta function.
The best way to get a feeling for what Rota was talking about is to consider some examples. The chromatic polynomial $\chi(n)$ of a graph is the number of ways to label the vertices of the graph with the numbers 1 to $n$ in such a way that adjacent vertices get distinct labels. It is not quite trivial, but also not difficult, to show that $\chi(n)$ is a polynomial function of $n$ (hence the name). Finding the chromatic number of the graph (a classical combinatorial problem, the most famous instance of which is the four-color theorem) is equivalent to finding the smallest positive integer zero of $\chi(n)$.
The chromatic polynomial may be thought of as the characteristic polynomial of the cycle matroid of the graph, so you can ask more generally about the combinatorial meaning of the zeros the characteristic polynomial of any matroid or even of any finite graded partially ordered set. In many cases these turn out to be combinatorially interesting quantities.
Furthermore, as the above paper on the Rédei zeta function shows, one can even draw a formal parallel between these polynomials and classical zeta functions. It would be cool if the zeros of the chromatic polynomial could be shown to be analogous to the zeros of the Riemann zeta function; unfortunately, they're at best analogous to the poles of the Riemann zeta function, so it's not clear that this observation buys us anything. It's an interesting thing to think about, though; maybe a nontrivial connection between combinatorics and number theory can someday be established along these lines.
Two keyphrases that will turn up many references in a websearch are "Combinatorial Nullstellensatz" and "the polynomial method" (or, "the polynomial method in combinatorics"). I'm not certain this is what Rota had in mind, but it certainly qualifies as a "correspondence between combinatorial problems and problems of the location of the zeroes of polynomials."
EDIT: On reading the other answers, I'm certain this is not what Rota had in mind, but it still qualifies as a "correspondence...."