No funciona desde un principio aunque tal y como está montado parezca que sí. Al final está la solución:

Cuando pides la butaca 1 no la encuentra porque `Sala[0][0]` vale `0` y utiliza el valor por defecto de Posición, que no es mayor ni igual que `1`, por lo que te da el error.

El código hace esto:

    i = 0
    j = 0
    Aux = 1
    ButacaAsignada = 1
    Sala[0][0] == 0
    Sala[0][0] != ButacaAsignada

Como no hay ningún elemento en Sala que valga 1 el if no se ejecuta:

    if (Sala[i][j] == ButacaAsignada) {
    Posicion = Aux; fila = i;  columna = j;
    } Aux++;

Entonces las varibles quedan así:

    Posicion = 0
    fila = 0
    columna = 0

Y en este if, como `Posicion` es `0` ejecuta el else dando el mensaje de Butaca Restringida.

    if (Posicion >= 1) {
    Sala[fila][columna] = 99;
    }
    else {
    System.out.println("Butaca restringida"); 
    }

La segunda vez cuando pides la butaca 5 tampoco la encuentra porque `Sala[0][4]` también vale `0`. El código hace esto cuando llega a la 5ª posición:

    i = 0
    j = 4
    Aux = 5
    ButacaAsignada = 5
    Sala[0][4] == 0
    Sala[0][4] != ButacaAsignada

El resto queda igual.


Cuando pides la butaca 2 la encuentra y le da a `Posición` el valor de `2` y a `Sala[0][1]` el valor `99`.

    i = 0
    j = 1
    Aux = 2
    ButacaAsignada = 2
    Sala[0][1] == 2
    Sala[0][0] == ButacaAsignada

Entonces el if se ejecuta:

    if (Sala[i][j] == ButacaAsignada) {
    Posicion = Aux; fila = i;  columna = j;
    } Aux++;

Entonces las variables quedan así:

    Posicion = 2
    fila = 0
    columna = 1
    Sala[0][1] = 99

Cuando pides dos entradas y vuelves a pedir la butaca `1` no la encuentra de nuevo:

    i = 0
    j = 0
    Aux = 1
    ButacaAsignada = 1
    Sala[0][0] == 0
    Sala[0][0] != ButacaAsignada

Igual que al principio como no hay ningún elemento en Sala que valga 1 el if no se ejecuta:

    if (Sala[i][j] == ButacaAsignada) {
    Posicion = Aux; fila = i;  columna = j;
    } Aux++;

Pero resulta que `Posición` sigue valiendo `2` desde el ciclo anterior, por lo que vuelve a asignar un `99` a la segunda butaca sin dar error porque la única validación que haces es si el valor de Sala es mayor o igual a 1.

    Posicion = 2
    fila = 0
    columna = 1
    Sala[0][1] = 99


Te recomiendo que `Posición` la reinicies a `0` en cada bucle y que en el if compares `Aux`, que es la que te da la posición en lugar del valor de `Sala` y puedes ver en los ejemplos de arriba que su valor coincide con el que estás buscando:

    do {
    System.out.println("Elija número de butaca: ");
    ButacaAsignada = Entrada.nextInt();
    Aux = 1;

    Posicion = 0;

    for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 11; j++) {

    if (Aux == ButacaAsignada) {

    Posicion = Aux; fila = i;  columna = j;
    } Aux++;
    }
    }

    if (Sala[fila][columna]>= 1) {

    Sala[fila][columna] = 99;
    }
    else {
    System.out.println("Butaca restringida"); 
    }
    Contador++;
    } while (Contador <= Compra);
    for (int i = 0; i < 4; i++) {
    System.out.println();
    for (int j = 0; j < 11; j++) {
    System.out.print("[" + Sala[i][j] + "]" + "  ");
    }
    }

Un saludo