WordPress navigation only shows post of page one, even if on page two

Question

The problem is $q is and array and $orderby is a string. So $q.$orderby doesn’t make sense. (Untested) but remove $orderby and try

$q['orderby']='title';

(The orderby key can have any value given in this list in the Codex.). Also, it would be neater to use this syntax:

$q = array(
    'category__not_in'=> array($category_id),
    'paged' => $paged,
    'orderby'=>'title',
);
query_posts($q);

Update

If you you are trying to make this compatible with the WP-PostRatings plug-in, instead of using the query string&r_sortby=highest_rated&r_orderby=desc, you can put it in array format:

$q = array(
    'category__not_in'=> array($category_id),
    'paged' => $paged,
    'meta_key' => 'highest_rated',
    'orderby'=>'meta value',
    'order'=>'DESC',
);
query_posts($q);

*Note, I’ve not tested this nor checked the plug-in’, but ‘highest_rated’ should be the meta key of the post’s rating. See the Codex for more details.*