How to fix SQL Agent Job using Windows Security after password change
Figured it out.
The job step is also using a Proxy account, which is the same account. So you need to change the proxy account credentials as well.