I have had exact same issue with my customer today but the error was slightly different. "This file format is not supported. Only .csv file format is supported." (see attached error)
We tried several different things to get it to upload with the same result each time. We have already tried editing the template directly. The CSV file can be sent for inspection if needed.