The DataValidation records of any given sheet must be written together (with no intervening records). POI 3.1 does not enforce this - new DVRecords are added just before the EOFRecord, which is not quite the right place. One way to observe this bug: Create a workbook in Excel. Add data validation to one cell. Delete the row containing that cell. Save. Open with POI, add data validation to a cell. Save. Open in Excel. An error will be reported.
Fixed in svn r681530