Thanks dean, I had missed that as it was between two of my posts that I thought were back to back
I found the log and the name was being resolved just fine. The problem was apparently the firewall. The thing throwing me off from looking into that was that the client couldn't talk to either my existing server (which other clients are already talking to) or the new one I am moving to (which this was the first client to try to talk to it).
I have two issues to still report though:
1 - On my existing server, even though other machines could talk to it fine, the new client I was installing was failing to connect. I tried multiple times and it just would not connect. Eventually, without any changes to my DNS or my firewall on the existing server, things just started working. This makes no sense to me but has been the experience with a couple of my client installs : They fail for a while and then just start working for no reason.
2 - On my new server, I did realize that the firewall was not opened for ANY cqc apps. Doesn't CQC setup on a master server setup the firewall?
Thanks for all the help. At least I got the 3500 talking to my existing server and I know that the first thing to tackle on the new one is the firewall ports.