We have found the problem. If you set the default Save format under Options
to Excel 97-2003, any newly created workbooks will be limited to the 65536
rows. I changed the default Save format to xlsx and now it creates new
workbooks in the new format with 1 million+ rows.

It makes sense, but I didn't associate the Save default with the workbook
creation.

Thanks to everyone for the assistance.