You may experience difficulty with new accounts not being able to log on until AD replication takes place when the account is created in a different site for example. To my knowledge, this would not result in a domain not available error though. This seems more like an issue with the computer not being able to find a domain controller or global catalog to log the user on. In Windows 2000 Server, a global catalog server is required when a user logs on for the first time to verify universal group memberships. This dependency is removed in Windows Server 2003 with universal group membership caching on domain controllers but this features is not enabled by default.
The reason that new users are able to log on after first logging on and changing their password at one of your workstations is because some changes such as password lockout and password changes are replicated immediately in AD.