When that happens to me the first thing I do is select "Print as image" in Reader's File > Print > Advanced menu. There are a couple of 100kb tax return PDFs I receive every month that simply will not print any other way, though I have lots of memory in the computer and the printer. I don't really know why -- it might have something to do with the way the fonts were handled when the documents were created.
On the other hand, I routinely get multi-page 50-100mb PDFs with lots of graphics which print perfectly without that selection. I don't use "Print as image" as my default setting since it's much slower, and the printed output is not quite as sharp (bitmap).
If you still get the error with "Print as image" selected, someone with more expertise will have to jump in to help.
Ned
