Seguramente el problema es que estás tratando de asignar `checked` con base en el valor actual de cada _checkbox_ en vez del "Seleccionar todo", de forma que no importa cuáles estén marcados y cuáles no, siempre se van a poner todos iguales.

Otra mejora que probablemente necesitas en tu script es cambiar clase de la etiqueta cuando se marcan o desmarcan individualmente:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

    // Marcar o desmarcar todos los checkboxes
    $("#todos").on('click', function() {
        // Obtener valor que se aplicará todos en la tabla
        let checked = $(this).prop('checked');
        $('#table_Permisos input[type="checkbox"]').each(function() {
            // Marcar o desmarcar
            $(this).prop('checked', checked);
            // Agregar o quitar clase
            if(checked) {
                $(this).parents('label').addClass('active');
            } else {
                $(this).parents('label').removeClass('active');
            }
        });
    });

    // Cambiar clase de etiqueta al marcar o desmarcar checkbox
    $('#table_Permisos input[type="checkbox"]').on('click', function() {
        if($(this).prop('checked')) {
            // Esta marcado, agregar clase
            $(this).parents('label').addClass('active');
        } else {
            // Esta desmarcado, quitar clase
            $(this).parents('label').removeClass('active');
        }
    });

<!-- language: lang-css -->

    label.active {
      background:#00a;
    }

<!-- language: lang-html -->

    <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.0/jquery.min.js"></script>
    <table id="table_Permisos">
      <tr>
        <td><label><input type="checkbox"></label></td>
        <td><label><input type="checkbox"></label></td>
        <td><label><input type="checkbox"></label></td>
      </tr>
    </table>
    <label><input type="checkbox" id="todos"> Marcar / desmarcar todos</label>

<!-- end snippet -->