How is the result of this TRUE? Condition: Customer : Balance (Base) > Customer : Credit Limit (The setting to count unbilled orders against the credit limit is OFF)

Is there activity on this customer in more than one currency? If a lot of the activity on this customer is in a non-functional currency, that could be your issue. I'd add actions to the workflow to store the values for each amount in a workflow field so you can see what amounts it's using for the comparison. Then you can backtrack from there to figure out how it's calculating the numbers it's using.