Try to open File / Options / Trust Center / Add-ins and disable all add-ins. Restart Excel and check if problem persists
If this did not help Go to Option / Add-Ins select from drop down menu COM Add-Ins and disable all.
Is the problem reproducible on other computers? I run Excel 2010 on Parallels on a MacBook Pro if it would help.
Is any of the conditional formatting being set by macros? If so, be aware that you generally need to select the cell being formatted before the macro applies the conditional formatting. The need to select the cell first is especially important if the conditional formatting uses relative addressing.
It may also be that the relative addresses in a conditional formatting "formula is" criteria are falling off the edge of the worksheet if you delete columns or rows.
Does the workbook contain a gazillion styles? Style corruption may be causing the crashes despite the error message to the contrary.
No, I don't use styles at all.Pretty much nobody uses styles. But they nevertheless multiply like rabbits as a workbook is edited over the years, especially so when you import worksheets from other workbooks. I've encountered workbooks with thousands of styles, none of which were used by anybody, and when they were deleted the sun came out, a rainbow appeared and the birds started chirping.
Restart Excel and check if problem persists
If this did not help
Go to Option / Add-Ins select from drop down menu COM Add-Ins and disable all