DG,
I had no problem creating a 4×6 picture package for a 13×19-inch page. Using 0.5-inch top, bottom, and side margins with 0.0-inch gutters between the prints, 9 images can be fit on one sheet. Here is the layout data for the file that I created:
I 13 19
(9) 4×6
0.5 0.5 4 6
4.5 0.5 4 6
8.5 0.5 4 6
0.5 6.5 4 6
4.5 6.5 4 6
8.5 6.5 4 6
0.5 12.5 4 6
4.5 12.5 4 6
8.5 12.5 4 6
I’ll add also that this "worked" in the context of the proper layout being provided in Photoshop, but I did not try to actually create and print such a package. Something to consider, depending upon the problems you’re having, is whether your printer will support full bleed vs. some minimum margin width. I believe my Epson 1270 has a 0.5 inch print margin, so that’s why I chose that value and used 0-inch gutters between the images. If you can print full bleed, then you may be able to add in some gutter space and decrease your margins.
Hope that helps,
Daryl