WORKAROUND 1:
Because the old CSRs still see the previous workflow rules, just for the old CSRs try to
- Select a user and give him the Approval Override privilege to make the status transfer OR
- Select a user from the original Approval list which can submit the approval.
WORKAROUND 2 (adopted by the customer):
Keeping in mind that this issue of not getting the rule satisfied is only limited to the case where the flag has been removed the "Required Approval" and not old CSRs are stuck where approvals are still required.
To give to a couple of lead developers override privilege. So, for all those stuck CSRs, the lead developers are helping moving the workflow step by passing the approval.