Why does the difference modifier not work on objects with many vertices, but will on a subset of those vertices?
I solved my problem by simply subsurfing the cylinders I used to make the larger object.

Explanation:

In the original design, you can see that the circular faces are whole (not subdivided into quads or triangles). In search of another solution using the knife projection tool, I discovered that it does not work well on whole faces, and subdividing the face was the solution there. It then occurred to me that subdividing faces might help the boolean modifier approach. In fact it did work: the only other caveat was that the top surface of the cylinders aren't subdivided by the Subdivide command - you have to use the Subdivide Surface command first.