Please post sample code to reproduce the problem.

The following code works fine to me:

    public static void main(String[] args) throws Exception {
        HSSFWorkbook wb = new HSSFWorkbook();
        HSSFSheet sh = wb.createSheet();
        for (int i = 0; i < Short.MAX_VALUE + 5; i++) {
            HSSFRow row = sh.createRow(i);
            for (int j = 0; j < 3; j++) {
                HSSFCell cell = row.createCell(j);
                cell.setCellValue("cell[" + i + "," + j + "]");
            }
        }
        for (int j = 0; j < 5; j++) {
            sh.autoSizeColumn(j);
        }
    }

Yegor

following code is failing with same exception : 

	public static void main(String[] args) throws Exception {
        HSSFWorkbook wb = new HSSFWorkbook();
        HSSFSheet sh = wb.createSheet();
        for (int i = 0; i < 65535; i++) {
            HSSFRow row = sh.createRow(i);
            for (int j = 0; j < 3; j++) {
            	CellStyle cellStyle = wb.createCellStyle();
            	CreationHelper createHelper = wb.getCreationHelper();
            	cellStyle.setDataFormat(createHelper.createDataFormat().getFormat("m/d/yy h:mm"));
                HSSFCell cell = row.createCell(j);
                cell.setCellStyle(cellStyle);
                Date date = new Date();
                cell.setCellValue("cell[" + i + "," + j + "]");
            }
        }
        for (int j = 0; j < 5; j++) {
            sh.autoSizeColumn(j);
        }
        FileOutputStream fileOut;
		try {
			fileOut = new FileOutputStream("workbook_MaxLimitTest4.xls");
			wb.write(fileOut);
		    fileOut.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		catch (IOException ie) {
			ie.printStackTrace();
		}
		System.out.println("Done");
    }

The maximum number of cell styles in a workbook is 4000, see http://office.microsoft.com/en-us/excel-help/excel-specifications-and-limits-HP005199291.aspx

Cell Styles must be shared. Do not create per-cell, otherwise you will get a “Too many styles” error in Excel when opening your workbook. Think of Cell Styles like CSS and create them like that.

http://poi.apache.org/faq.html#faq-N100EF

Yegor

*** Bug 50853 has been marked as a duplicate of this bug. ***