I banged my head against the desk for way too long trying to figure out this issue. While trying to authenticate with Netsuite’s REST API instead of SOAP, I got the same INVALID_LOGIN_ATTEMPT error.
The fix? My account ID, which was a sandbox and included the letters S and B, had to be capitalized. I was using lowercase letters. Changing them to uppercase letters did the job!