Yeah I got the IP part... it was more related if you had clients connecting into the server on Terminal Services (tcp/3389), http (tcp/80), etc... ie I really didn't know what you meant by "client" or how you were expecting them to talk
What is the first DNS server that your clients are getting from the linksys? Is it your local one or is it the caching one built into many of the Linksys routers? Also what version of the OS are your clients running? If you're running Vista or 7 you should be able to look at the performance section within the control panel to see if you can narrow down what service is causing the delay... a login time that long should be noted as a performance degradation within the logs there.