I found that our anti-virus software that is installed locally on each machine also has a firewall. Even though I had the Windows Firewall turned off, this was blocking the Service Locator, NI-Pal and a few other NI services. I changed the permissions on the firewall and now everything is working.
Thanks for the responses and help.
