Sorting Custom Posts on Archive page with pagination

I had the same problem.
I was using a form to sort the data, and a pagination using paginate_links. My solution was to use $_SESSIONS to store the $_POST data from the sort (instead of just parsing the $_POST data), and set the form action to get_permalink(). Make sure to unset your session if you are not using pagination or if you are not $_POST ing the sort form.

<script>
function submitform(val) {
    document.getElementById('sort-option').value = val;
    document.getElementById('form-sort').submit();
}
</script>

<form id="form-sort" action="<?php echo get_permalink(); ?>" method="post">
    <ul>
        <li>Sort By:</li>
        <li><a href="#!" onclick="javascript: submitform('newest');">Newest rating</a>
        </li>
        <li><a href="#!" onclick="javascript: submitform('highest');">Highest rating</a>
        </li>
        <li><a href="#!" onclick="javascript: submitform('lowest');">Lowest rating</a>
        </li>
    </ul>
    <input type="hidden" id='sort-option' name="sort-option" value="">
</form>

–

if($wp_query->get('page') == 0 && empty($_POST) && !empty($_SESSION)) session_unset();

if(!empty($_POST) || !empty($_SESSION)) {

    switch($_POST['sort-option']) {
        case 'newest':
            $_SESSION["sort"] = SORT_DESC;
            $_SESSION["sort_by"] = 'review_date';
            break;
        case 'highest':
            $_SESSION["sort"] = SORT_DESC;
            $_SESSION["sort_by"] = 'rating';
            break;
        case 'lowest':
            $_SESSION["sort"] = SORT_ASC;
            $_SESSION["sort_by"] = 'rating';
            break;
    }

    foreach($reviews as $k => $v) {
        $column_id[$k] = $v[$_SESSION["sort_by"]];
    }

    array_multisort($column_id, $_SESSION["sort"], SORT_NUMERIC, $reviews);

}

If you show some code, I might be able to help you more.