Updating this thread with the resolution steps performed by our team in this scenario.
Issue:
After updating the storage access keys, the job submission was failing with 403
Cause:
The values for the storage keys was cached in the storage connection strings at the backend
Resolution:
The engineering team manually deleted the cached storage keys from the backend
@Jim-9799 Please feel free to accept this as answer so any other user can follow the steps.