Being pretty smart - he tried exporting out a blank template from GP and then importing it back in, and still got the error. He compared all the columns one by one and they all seemed same. He tried deleting columns, using different version of Excel ... but could not get rid of the error.
So we started researching and found that their Fiscal Periods were named - "January", February", "March" ...
On export, excel automatically converted the columns to DATE format each time. GP, however, was looking for TEXT format.
The resolution from Microsoft to fix this is -
1. In the Excel worksheet, highlight all the column headers for the periods.
2. For Office 2003: On the Format menu, click Cells.
For Office 2007: Right click on cell and select Format cell..
3. On the Number tab, click Text in the Category list.
4. Click OK.
5. If the cells are changed to numbers, re-enter the period headers to match the fiscal period setup.
I do appreciate GP support identifying the problem and offering a solution. I can understand why GP has a problem, and I can understand why 90% of the users would not figure this out themselves. This is just excel being Mr Smartass. All over again.