If you are sending messages over HTTP then there is a chance you may be behind a proxy server which prevents you making a direct connection to the destination server.
This is no big deal - Internet-enabled products such as Internet Explorer and MSMQ always check for any proxy settings so they know how to get out onto the Web. Specifically they check:
If you have MSMQ messages in an outgoing queue that remains in a Waiting to Connect state then you may want to check the proxy settings are correct.
Here for reference are a couple of Knowledgebase articles for different products that discuss resolving the same root cause (bad WinHttpSettings proxy value):