Slow AFP authentication since latest patches with Leopard clients (10.5.5 & 10.4.11 Server)

Recently we have found slow slow slow authentication to 10.4.11 and 10.5.5 servers from 10.5.5 clients. A 10.4.11 client has no problem and authenticates immediately. A 10.5.5 client takes up to 2 minutes both to 10.5.5 Server and 10.4.11 Server, but to a 10.4.11 server that does not have the latest patches applied, there is no problem and it pulls right up. This is all connecting to the IP addresses of the servers not DNS names.