The method sheet.autoSizeColumn for HSSF does not respect formats for dates. It rather tries to format the date as a numeric, fails and falls back to a very simple to-string-transformation:

try {
  NumberFormat fmt;
  if ("General".equals(format))
    sval = "" + value;
  else
  {
    // --> fails, because the format is no Decimal Format
    fmt = new DecimalFormat(format);
    sval = fmt.format(value);
  }
} catch (Exception e) {
  sval = "" + value;
}

Hence, the width for date cells is not calculated corretly. 

Sample Code ist here:
//-----------------------------------
Workbook workBook = new HSSFWorkbook();
Sheet sheet = workBook.createSheet("First Sheet");

Row row = sheet.createRow(0);
Cell cell = row.createCell(0);
cell.setCellValue(new GregorianCalendar(2010, 7, 3));
DataFormat dataFormat = workBook.getCreationHelper().createDataFormat();
CellStyle cellStyle = workBook.createCellStyle();
cellStyle.setDataFormat(dataFormat.getFormat("dd.mm.yyyy"));
cell.setCellStyle(cellStyle);

row = sheet.createRow(1);
cell = row.createCell(0);
cell.setCellValue("small");

sheet.autoSizeColumn(0);

workBook.write(outputStream);
//-----------------------------------