User account can't access one server via

Here we have a Lotus Notes/Domino server which everyone in the company connects to via tcp/ip. I recently set up a new user and installed Notes client on his workstation, but it will not connect to the Domino server, though it can browse the server shares just fine. If I log into the workstation on my domain admin account the workstation will connect to the Domino server. If I log onto the workstation as the user domain account, it will not connect (but will browse).
Any ideas?