Are the Conditional Formatting rules that turn the cells green and apply the border the same CF rule, or different CF rules?
If they are different rules, do they follow the same exact formula on the exact same range?
And did you specifically choose the "Outline" border option (instead of picking each border line separately)?