PROGMEM Corrupted Array
Just a follow up in case someone else has the same problem. One solution is Nick's answer in his comment, which grabs the far addresses first in the setup, storing them in an array, and using them. I 

// Each array contains 32000 values
const byte VALUES_1[] PROGMEM = { 1, 0, 1, .... 0 };
const byte VALUES_2[] PROGMEM = { 1, 1, 0, .... 0 };
const byte VALUES_3[] PROGMEM = { 1, 0, 1, .... 1 };
const byte VALUES_4[] PROGMEM = { 1, 0, 1, .... 1 };
const byte VALUES_5[] PROGMEM = { 1, 0, 1, .... 1 };

long VALUES[] = { 0, 0, 0, 0, 0 };

const long ARR_LEN = 32000;
long index = 0;

void setup() {
  Serial.begin(57600);
  while (!Serial) {}

  VALUES[0] = (long) pgm_get_far_address(VALUES_1);
  VALUES[1] = (long) pgm_get_far_address(VALUES_2);
  VALUES[2] = (long) pgm_get_far_address(VALUES_3);
  VALUES[3] = (long) pgm_get_far_address(VALUES_4);
  VALUES[4] = (long) pgm_get_far_address(VALUES_5);
}

byte readNextValue() {
  if (index &gt;= 160000L) {
    return -1;
  }

  Serial.print(index);
  Serial.print(" ");

  long arr = index / ARR_LEN;
  long i = index % ARR_LEN;
  index++;

  byte j = pgm_read_byte_far(VALUES[arr] + i);
  Serial.println(j);

  return j;
}

void loop() {
  // put your main code here, to run repeatedly:
  readNextValue();
}


This runs perfectly with all bytes correct. The better answer would be to convert the bytes into bits like everyone else was saying in order to save memory space.