I just opened up iPhoto 6, selected two photos, went to the Print dialog, selected Standard Prints, size 4x6, and unchecked One Photo Per Page. Looked fine and I didn't get any warnings. The warning was a yellow triangle with an exclamation point, right? I think if you mouse over or click the yellow warning, it provides explanation tooltip text. Usually when I receive that warning, it has to do with the photo's resolution being too low.
If this is some sort of iPhoto bug also, OmniGraffle a try. Seems to work nice for cramming a large number of photos onto photo paper, especially with the nice auto-alignment features. I used to use AppleWorks in OS9 to do that kind of photo printing before I tried the version of OmniGraffle that came free with my Mac.
EDIT: seems to only happen when trying to print two of the same image. When I select two different images and choose duplicate, it shows the first photo twice on the same page with no triangle. You could right click on the image and choose "Duplicate" and then select the duplicate and the original image and print both of those on the same page, which seems to not have the bug.