It would be possible that not only 1 approval is needed?
Do you use Workflow User Group with more than one approver? Approval Chain? or just Direct Approval?
Can you check if you have in the workflow a response when the Approvals are = 0, that Remove the Record Restriction? If you miss this one, the Record Restriction is not released.
Please check this and let me know.