Access to remote computer's MSMQ gives "Remote computer is not available"

We have a windows application that runs on a server and accesses 4 other servers (all of them are members in the domain) to get the messages in each of their private queues. We've just installed a new server, and for some reason when the application tries to access that computer, it gets a "Remote computer is not available" message.
The application accesses the other servers with a user who is an admin domain user.
Has anyone encountered such a problem, or have a clue as to what could be causing it?

From stackoverflow Lea Cohen

• Could it be a firewall issue?

  http://support.microsoft.com/kb/183293

  From Eric Z Beard

• Have you fired up a packet capture tool such as Microsoft Network Monitor or Wireshark and looked at the traffic going to and from the system that gets the error? That's often the surest way to see what is going on without alot of time consuming experimentation.

  I would set up a capture from the box getting the error, run until you get the error, and immediately stop the capture. Set a filter to look at just the traffic to and from that system. If you can't install the capture tool on the box itself, make sure you place it on the network in a way that it will still be able to see all the traffic from that box. (I.e. don't put it on an adjacent port on a switch, because the switch's job is to insulate each ports traffic from each other).

  IF you see no actual traffic being sent to the remote server in question, then you probably have a naming/directory/DNS type issue. I.e. the local server can't figure out where the other one is. Since this is a Windows domain type situation, I'd start looking in Active Directory for clues.

  IF you see traffic going out to the remote server, but you never see even one packet coming back from it before the failure, then you probably have a firewall issue either on the remote box or on the route from here to there.

  IF you see traffic going back and forth to the remote server but then it stops, you'll need to dig into those packets and see what low-level error codes might be present in the traffic. Both NETMON and Wireshark have good decodes for the Microsoft protocols so you should be able to see exactly what is happening. If you're not familiar with these protocols, you might want to first capture a correctly working connection to one of the other servers so you can compare.

  From Tim Farley

• Probably way too late for this thread, but I found the answer to this here: http://blogs.msdn.com/johnbreakwell/archive/2008/07/10/getting-msmq-messages-out-of-windows-server-2008.aspx

  From pattermeister

• The problem is finally solved, and it was solved accidentally: Apparently there was some confusion in the DNS server, and the cache server had difficulty accessing the correct server. Our webmaster corrected al the server names, and that also solved the MSMQ problem.

  From Lea Cohen