Please, post the error message. If it is Integrated authentication and the message "Login Failed for User NULL" or Login Failed for User "Dude'sComputer\IamTheAdmin" then they are not logging in as users in the same domain. For example, if some dude logs in as a domain user and you gave permissions for domain users, he will be able to connect. If the same dude logs in locally to his computer or some other domain as a local admin with the name "IamTheAdmin", as them, developers, do, in this case he will get these messages. What particular message depends on the domain trust.
Also in 2005 logins can be locked out. Check the login properties for those who can not connect, if there is Locked Out checked on Status tab