301 Redirect Problem

I removed a ‘native and aboriginal news’ category along with all it’s posts from my website – ‘www.ryanpaul.ca’ to a new domain – ‘www.intertribaltimes.ca’. I changed my permalink structure, search engines indexed the new change and then stupidly I changed it again to the structure I really wanted.

Anyway… I currently have this in my header.php to do 301 redirects. I can’t delete the posts in the ‘native and aboriginal news’ category from my site (ryanpaul.ca) because the redirects won’t work – the following php only works when the posts is on the source and the destination server.

Does anyone know of a way I can do this without needing the posts to exist on the old server?

<?php
$category = get_the_category();
$categoryname = $category[0]->cat_name;
$categoryslug = $category[0]->category_nicename;
$postslug = $post->post_name;
if( $categoryslug == 'native-and-aboriginal-news' && is_single() ) { ?>
<?php
  header("HTTP/1.1 301 Moved Permanently");
  header("Location: http://www.intertribaltimes.ca/native-and-aboriginal-news/$postslug");
?><?php } else { ?><? 

$url = 'http://'.$_SERVER["HTTP_HOST"] . $_SERVER["REQUEST_URI"];
if( is_single() && $url != "http://www.ryanpaul.ca/$categoryslug/$postslug/" ) {
  header("HTTP/1.1 301 Moved Permanently");
  header("Location: http://www.ryanpaul.ca/$categoryslug/$postslug/");
}

?><?php } ?>