Pagination Issues using WP_Paginate Plugin

Your solution here is most correct..

    if(have_posts()){ $paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
query_posts($query_string . "&cat=4"); 
while(have_posts()){ 
the_post(); global $more; $more = 0;

…but has some errors. Try:

$paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
$category = get_category_by_slug('your-category-slug');
query_posts(array('paged' => $paged, 'cat' => $category->term_id)); 
while(have_posts()){ 
    the_post(); 
    global $more; 
    $more = 0;
    //output here
}

Note, that using the category id directly isn’t going to work on WP VIP. Category ID’s won’t match what you have locally.