There are a few questions I'd like to ask here:
1. If I understand correctly, these are Windows terminals. Have you tried a PC using the Citrix client, and if so, how does it behave?
2. If you have a PC, is it able to immediately ping the Citrix server? (Undoubtedly it will be able to-I don't feel this is a routing issue, either it would still be slow after connect, or subsequent connections from the same client would likely be faster).
3. With the PC, after the initial "good" test, force an ip address change, deliberately unconfigure WINS (disable DHCP) and reboot. Try to connect again.
What I'm hypothesizing here is that on the server side, while the connection is being set up, the server is trying to resolve the client name several times and is must time out for each attempt. A Winterm may not be configured to register in WINS. A further test would be to put the client addresses in the %SYSTEMROOT%\system32\drivers\etc\hosts file, copied from hosts.sam. This should allow the server to resolve them regardless of whether they are in WINS. Since you indicate that you're coming through a NAT connection, all of this may be mute, and you may need to register the NAT device in your hosts table if there is no resolvable entry in WINS. Test that it's working by trying to ping by name. To figure out what address to register, do a netstat -a from the command line on the server and hunt for the address the client is coming in from. If your server is busy, this may be tough if you aren't fairly aware of the addressing scheme at your site - you may need to ask for help from your network group.
I notice several people above making reference to profile sizes, then correcting themselves for profiles being local. The original statement was very clear - "5 minutes before they see the login screen". No profiles involved at all.