How can I simplify this set of if statements? (Or, what’s making it feel so awkward?)

One reason it looks like a lot of code is that it is very repetitive. Use variables to store the parts that are repeated, and that will help with the readability:

private List<Foo> parseResponse(Response<ByteString> response) {
    Status status = response.status();
    int code = status.code();
    boolean payloadAbsent = !response.payload().isPresent();

    if (code != Status.OK.code() || payloadAbsent) {
      if (code != Status.NOT_FOUND.code() || payloadAbsent) {
        LOG.error("Cannot fetch recently played, got status code {}", status);
      }
      return Lists.newArrayList();
    }
    // ...
    // ...
    // ...
    return someOtherList;
}

Edit: As Stewart points out in the comments below, if it’s possible to compare response.status() and Status.OK directly, then you can eliminate the extraneous calls to .code() and use import static to access the statuses directly:

import static Namespace.Namespace.Status;

// ...

private List<Foo> parseResponse(Response<ByteString> response) {
    Status status = response.status();
    boolean payloadAbsent = !response.payload().isPresent();

    if (status != OK || payloadAbsent) {
      if (status!= NOT_FOUND || payloadAbsent) {
        LOG.error("Cannot fetch recently played, got status code {}", status);
      }
      return Lists.newArrayList();
    }
    // ...
    // ...
    // ...
    return someOtherList;
}

Regarding the question of what to do with the duplication of the payloadAbsent logic, Zachary has provided some good ideas that are compatible with what I have suggested. One more option is to keep the basic structure, but make the reason for checking the payload more explicit. This would make the logic easier to follow and save you from having to use || in the inner if. OTOH, I’m not very keen on this approach myself:

import static Namespace.Namespace.Status;

// ...

private List<Foo> parseResponse(Response<ByteString> response) {
    Status status = response.status();
    boolean failedRequest = status != OK;
    boolean loggableError = failedRequest && status!= NOT_FOUND ||
        !response.payload().isPresent();

    if (loggableError) {
      LOG.error("Cannot fetch recently played, got status code {}", status);
    }
    if (failedRequest || loggableError) {
      return Lists.newArrayList();
    }
    // ...
    // ...
    // ...
    return someOtherList;
}