Write unit tests for interface or implementation?

Given the following test scenario, where I have the interface:

public interface UserService {

    /**
     * Registra um usuário no sistema.
     * 
     * @param user
     *            Usuário à ser registrado. Não deve ser {@code null}
     * @return Inteiro maior que zero representando o id do usuário registrado,
     *         ou 0 caso o registro falhe
     * @throws IllegalArgumentException
     *             Caso o usuário seja {@code null}
     */
    long register(User user);
}

And a possible implementation that meets the interface's javadoc contract:

public class UserServiceImpl implements UserService {
    private UserDao userDao = // Inicializa ou injeta o DAO

    @Override
    public long register(User user) {
        if (user == null) {
            throw new IllegalArgumentException("Usuário não pode ser null");
        }

        try {
            userDao.insert(user);
            long insertedId = user.getId();
            return insertedId;
        } catch (SomeException e) {
            logger.error("Erro ao registrar o usuário " + user.getUsername(), e);
            return 0;
        }
    }
}

By the time I write my unit tests for the register(User user) method, should I test the UserServiceImpl implementation directly? For example:

public class UserServiceImplTest {
    private UserService service;

    @Before
    public void setUp() {
        service = new UserServiceImpl();
    }

    @Test
    public void shouldReturnIdGreaterThanZero() {
        User user = // Inicializa um usuário pronto para inserção
        long insertedId = service.register(user);

        Assert.assertTrue(insertedId > 0);
    }
}

Or just test the interface by injecting the implementation through a ServiceLocator, for example?

public class UserServiceTest { // Note que até mudei o nome da classe de testes
    private UserService service;

    @Before
    public void setUp() {
        service = // Obtém a implementação através de algo parecido com um ServiceLocator
    }

    @Test
    public void shouldReturnIdGreaterThanZero() {
        User user = // Inicializa um usuário pronto para inserção
        long insertedId = service.register(user);

        Assert.assertTrue(insertedId > 0);
    }
}

Which approach should I take? It is worth mentioning that new implementations may arise, however I refer only to the UserService interface in my domain code.

Some code snippets and javadoc were omitted to simplify the code.