What could be causing my wp_query pagination to break?

This might happen because you need to include the pagination information when you run custom queries with query_posts. Because custom query_post commands ignore any default values of the query_posts command. Here is an example of a query i have used to solve this problem in a simpler case (just to exclude a single category from the query):

   <?php
         if ( is_home() ) {
            $paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
            query_posts("cat=-19&paged=$paged");
         }
    ?>

Here is an example of how you can include this in your query. Don’t know if this works for you, try it out and give me feedback. 🙂

    $paged = (get_query_var('paged')) ? get_query_var('paged') : 1;

    query_posts(
    array_merge(
        $wp_query->query,
        array(
            'category__and' => $pladvsearchcatids,
            'meta_key' => 'price',
            'orderby' => 'meta_value_num',
            'meta_compare' => '<=',
            'meta_value' => $plbudget,
            'order' => 'DESC',
            'paged' =>  $paged
        )
    )
);