Cambiar la prioridad de un registro, se puede pensar como la sucesión de los siguientes eventos:

 1. **"Sacamos el registro"**: por lo que, todos aquellos registros cuya prioridad sean mayor deben decrementarse en 1, es decir:

        UPDATE ACT_Agenda
          SET prioridad = prioridad - 1 
          WHERE prioridad > ?

 2. **"Agregamos el registro"**: por lo que, todos aquellos registros cuya prioridad sea mayor o igual debe incrementarse en 1, es decir:

        UPDATE ACT_Agenda
          SET prioridad = prioridad + 1 
          WHERE prioridad >= ?

#Solución:

Por [razones de seguridad](https://es.stackoverflow.com/q/18232/16597) sería optimo que usaras [sentencias preparadas](http://php.net/manual/es/mysqli.quickstart.prepared-statements.php), por lo que el código podría ser el siguiente:

    <?php
    //update.php
    include_once('../include/conexion.php');

    // Validamos que el registro existe y 
    // obtenemos la prioridad que tiene
    $query = "SELECT prioridad 
        FROM ACT_Agenda 
        WHERE id_agenda = ?";
    $stmt = mysqli_prepare($con, $query);
    mysqli_stmt_bind_param($stmt, "i", $_POST["pk"]);
    mysqli_stmt_execute($stmt);
    mysqli_stmt_store_result($stmt);

    if (mysqli_stmt_num_rows($stmt) == 1) {

        mysqli_stmt_bind_result($stmt, $prioridadAnt);
        mysqli_stmt_fetch($stmt);

        // Si se modifico la prioridad
        if ($prioridadAnt != $_POST['value']) {

            // Actualizamos todos los registros 1)
            $query = "UPDATE ACT_Agenda
              SET prioridad = prioridad - 1 
              WHERE prioridad > $prioridadAnt";
            mysqli_query($conn, $query);

            // Actualizamos todos los registros 2)
            $query = "UPDATE ACT_Agenda
              SET prioridad = prioridad + 1 
              WHERE prioridad >= $prioridadAnt";
            mysqli_query($conn, $query);
        }

        // Actualizamos la prioridad
        $query = "UPDATE ACT_Agenda 
            SET prioridad = ?
            WHERE id_agenda = ?";
        $stmt = mysqli_prepare($con, $query);
        mysqli_stmt_bind_param($stmt, "i", $_POST["value"]);        
        mysqli_stmt_bind_param($stmt, "i", $_POST["pk"]);
        mysqli_stmt_execute($stmt);
    }