Even if you need to make a more efficient tree design, it should not take 5 minutes unless you have a VERY slow network or VERY large tree. You are probably timing out on some operation. You didn't specify what your protocols and clients are, so this may not apply at all. According to Novell, NT/2000 clients perform asynchronous lookups to all available name services and do not use the "name resolution order" setting.
I had a similar problem caused by strange default behavior build in to outdated Win9x clients. We noticed the slow logins were occuring only when our ISP was down. Our DNS was hosted on our ISP's network. Even though we had all our Netware traffic on IPX, and explicitly configured Client32 to use IPX as the default protocol, we discovered that the client was trying to do a DNS name lookup of the server (and other SAPing hosts) before performing an IPX login. It was waiting for a response (which never came) for over 5 minutes. No matter how we configured the clients they would still try to perform the lookup and wait. (including the Client32 props for name resolution order, specifying NDS and SAP before DNS or SLP for lookups)
Upgrading out clients to 3.1SP2 solved the problem. Then when 3.2 came out, the problem reappeared, so we downgraded to 3.1SP2. In 3.3 the problem is fixed again. In addition, we have moved our DNS on-site.
The next troubleshooting steps I would try:
1.Make sure you're using the newest client
2.Assign DNS names to the servers to match their NW names
3.Sniff the wire to see if the client is repeating some kind of request during the delay period.
4.Monkey around with the name resolution order settings on the client if it's Win9x. Use what makes sense for your network.