Negotiate was my issue. After disabling Negotiate, and only allowing NTLM and Basic, I was able to successfully allow the users who were experiencing the problem to login properly.
In our web.xml file, we set the following init-param for our Filter (for anyone else who is interested):
Upon doing that, our filter only replied back to the client with a 401-Unauthorized error and WWW-Authenticate: NTLM WWW-Authenticate: Basic
We'll be replacing JRun with JBoss sometime in the future, so when that happens, we'll be able to re-enable Negotiate (and hopefully won't have this problem anymore).