Hi Calmeida,
On the last page of the Print Catalog dialog, for 'Files to Process:' you can choose: 'Current folder', 'Current tree' or 'Selected Files'. Of these, only 'Selected Files' will print the files in the order that they are currently displayed in the thumbnail listing.
When you print from a gallery, the Folder and Tree options should not even work (well, they don't work for me. The options are shown but when I use them, I see an error in the task list and no catalog is printed).
So, my suggestion would be to print from the regular harddisk folder. First, put the thumbnail listing in the desired order, then select all files (Ctrl-A), then call the Print Catalog function and on its last page, specify 'Selected Files'.
Hopefully that will also avoid the error message that you got when you printed from a gallery.