MSMQ write taking > 1 minute

We have an ongoing problem with message writes to MSMQ being very slow. Our queue is on Windows Server 2008 SP2. The queue is a public queue, addressed at "servername\queuename".

The code to send a message to the queue is

MessageQueue queue = new MessageQueue(Settings.Default.DefaultDestinationQueue);
queue.Formatter = new BinaryMessageFormatter();

queue.Send(message);

The message that we're trying to send is simply a "PublishMessage", as follows:

[Serializable]
public class PublishMessage {
    public int EntryId {get; set; }
}

We're seeing the messages actually reach the queue, but logging before and after shows that it's generally taking in excess of 1 minute for each message.

At this time, we can't see anything wrong with our queue configuration, but are not queuing experts–this is the first addition to this application. Anyone have any ideas?

Edit: Our server is running SP 2 (not SP1 that I originally stated). Running an instance directly on the machine hosting the queue is fast, any other is not.

Note: I've crossposted this at https://stackoverflow.com/questions/6083070/msmq-write-taking-1-minute