Sometimes you can have a problem where you can't remotely receive messages from another machine but don't know where to start troubleshooting.
Normally you will get something informative back as an exception, such as:
where it's usually obvious what needs to be fixed.
Probably the least helpful error message is the one that says "Service not available" when you're damned sure it is. First thing to check is which MSMQ service is throwing the exception - the one on the local machine performing the operation or the remote machine's service where the queue is hosted. Luckily MSMQ has error codes to help you distinguish so make sure your application is reporting the exception appropriately:
Remote MSMQ service offline
0xc00e0069 - MQ_ERROR_REMOTE_MACHINE_NOT_AVAILABLE
Remote machine unavailable
Local MSMQ service offline
0xc00e000b - MQ_ERROR_SERVICE_NOT_AVAILABLE
Once you know which service is unavailable, you bring in the relevant troubleshooting tools.
If the remote service is unavailable then Network Monitor is a good start to check that the client machine can actually contact the one hosting the queues or not. Receiving messages uses RPC (instead of the native MSMQ or HTTP protocols used for sending) so make sure you don't filter it out. Network traces help you highlight issues like DNS misconfigurations or restrictive firewalls preventing the RPC packets getting through. By default on Windows Server 2008, I don't think the Windows Firewall allows any incoming RPC traffic.
Troubleshooting a local service being unavailable is not as easy - it isn't very often that the cause is simply that the MSMQ service is not up and running. Also the exception may have occurred on the local machine, on a remote machine called by the local machine, or on a remote machine called by another remote machine (for example, should the queue host need to contact a domain controller). As mentioned above, MSMQ is using RPC so it can be useful to enable extended error information and make use of the extra returned data.
In all cases, you can also engage Microsoft PSS to have the MSMQ log files analysed. These binary files in the Windows\Debug directory contain logging from the MSMQ service and may contain useful information. They can only be converted to text files by Microsoft engineers so it is not possible to make use of these logs on your own.