Pagination Issues using WP_Paginate Plugin

So I have read more posts and articles about this issue than I care to admit and still nothing I can find works. Here is the issue – I can not get the pagination to advance and it shows all the same posts over and over – like I have seen in other posts.

Here is what I am using (2 seperate templates for different categories):

<?php
$paged = get_query_var( 'page' );
query_posts('cat=4&paged='.$paged);
if(have_posts()) { while(have_posts()) { the_post(); 
?>

It works fine , but then I go to the only other page on the site – which uses the same code in the loop, different category (3) and it does not work there, it is not a typo, etc.

I have also tired the following:

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;

OR

query_posts('cat=3&paged='.get_current_page());
  if(have_posts()){
  while(have_posts()){
  the_post();
  global $more;
  $more = 0;

With the get_current_page function, I used this hack, which I was told by WP VIP was not the way to do things (but it worked for both pages):

/* Get current page for paginaton navigation */ 
function current_page() {
 $pageURL = 'http';
 //check what if its secure or not
 if ($_SERVER["HTTPS"] == "on") {
 $pageURL .= "s";
 }
 //add the protocol
 $pageURL .= "://";
 //check what port we are on
 if ($_SERVER["SERVER_PORT"] != "80") {
 $pageURL .= $_SERVER["SERVER_NAME"].":".$_SERVER["SERVER_PORT"].$_SERVER["REQUEST_URI"];
 } else {
 $pageURL .= $_SERVER["SERVER_NAME"].$_SERVER["REQUEST_URI"];
 }
 //cut off everything on the URL except the last 3 characters
 $urlEnd = substr($pageURL, -3);
 //strip off the two forward shashes
 $page = str_replace("/", "", $urlEnd);
 //return just the number
 return $page;
 }