How about the problem of, given a polynomial equation in at least two variables and integer coefficients, figuring out whether it has any integer solutions. This has directed a lot of modern mathematics and, on the face of it, doesn't seem like it should be so hard.
Plus you can build off of this. They may remember that for two variable quadratics the real solutions form an oval or hyperbola or quadratic or two lines. In general you'll get some higher dimensional surface, and the "shape" of it (and how many "holes" it has) is closely tied with how many integer solutions there can be.