Which version of Excel are you using and can you show us the conditional formatting rules you've used for one of the cells in those two troublesome columns (please then also tell us the cell address), or can you zip and attach the workbook?
Okay, I can't open your zip file but the Excel version is the important piece of information here.
In Excel 2003 you can only have one condition resolving to TRUE. If you have multiple conditions returning TRUE then the first one that was added has precedence (Condition 1 > Condition 2, Condition 3). I see that you're familiar with VBA so, in "VBA terms", you could think of it like this:
If Condition1 Then
ElseIf Condition2 Then
ElseIf Condition3 Then
In Excel 2007, conditional formatting was given an overhaul and multiple conditions resolving TRUE is possible. In Excel 2003, I think the only way to get the effect you want would be to use VBA.