Timing single operation to not be repeated for a fixed time
First of all, it looks like as a workaround for another bug. You might want to fix that bug instead of this workaround.
Comments like the following are unnecessary:

 /**
 * Logger for this class
 */


It just repeats the code and forces readers to read more than necessary.
Service.getInstance() is repeated. Create a local variable for it.
Synchronizing on public objects (like RecoverServiceCommand.class) is error-prone.  I'd use a private lock object instead. See: Avoid synchronized(this) in Java?
A minor change could be extracting out a boolean needsRestart local variable which would make the intention of the expression a little bit more clear.

Reference: Chapter 6. Composing Methods, Introduce Explaining Variable in Refactoring: Improving the Design of Existing Code by Martin Fowler


  Put the result of the expression, or parts of the expression, 
  in a temporary variable with a name that explains the purpose.

Currently the code is tightly coupled with the Service and the Utils classes. If you want to write unit tests it's not too easy because it needs a working Service instance and it depends on the system time too. To make it easier to test you could pass the dependencies to the constructor:

private static final ReentrantLock lock = new ReentrantLock();

private final Service service;

private final Ticker ticker;

private final long updateInterval;

public RecoverServiceCommand(final Service service, final Ticker ticker, 
        final long updateInterval) {
    this.service = checkNotNull(service);
    this.ticker = checkNotNull(ticker);
    checkArgument(updateInterval &gt; 0, "updateIntarval must be bigger than zero");
    this.updateInterval = updateInterval;
}

@Override
protected void doExecute(final Object... arg0) throws CommandException {
    final long now = ticker.read();
    lock.lock();
    try {
        final boolean needsRestart = 
            (now - service.getLastUpdate()) &gt; updateInterval;
        if (needsRestart) {
            service.restartService(now);
        } else {
            log.warn("Messaging queues not restarted because "
                + "it was already restarted not so long ago");
        }
    } finally {
        lock.unlock();
    }
}


Here is a few tests with EasyMock:

import static org.easymock.EasyMock.expect;

import org.easymock.EasyMockSupport;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import com.google.common.base.Ticker;

public class RecoverServiceCommandTest {

    private EasyMockSupport mockery;
    private Service service;
    private Ticker ticker;

    @Before
    public void setUp() {
        mockery = new EasyMockSupport();
        service = mockery.createMock(Service.class);
        ticker = mockery.createMock(Ticker.class);
    }

    @After
    public void tearDown() {
        mockery.verifyAll();

    }

    @Test(expected = IllegalArgumentException.class)
    public void testInvalidUpdateInterval() throws Exception {
        final long invalidUpdateInterval = 0;

        mockery.replayAll();

        new RecoverServiceCommand(service, ticker, invalidUpdateInterval);
    }

    @Test
    public void testUpdateIsRequired() throws Exception {
        final long updateInterval = 100;

        final long currentTime = 300L;
        expect(ticker.read()).andReturn(currentTime);
        expect(service.getLastUpdate()).andReturn(199L);
        service.restartService(currentTime);

        mockery.replayAll();

        final RecoverServiceCommand command = 
            new RecoverServiceCommand(service, ticker, updateInterval);
        command.doExecute();
    }

    @Test
    public void testUpdateIsNotRequired() throws Exception {
        final long updateInterval = 100;

        final long currentTime = 300L;
        expect(ticker.read()).andReturn(currentTime);
        expect(service.getLastUpdate()).andReturn(200L);

        mockery.replayAll();

        final RecoverServiceCommand command = 
            new RecoverServiceCommand(service, ticker, updateInterval);
        command.doExecute();
    }

}


I've used the Ticker class from Guava. It's easy to mock it and it has a systemTicker which you can use in production code. The check methods are also in Guava.