I went through the same problem a few months back. After several different ways I finally found a way that worked. Try adding this to your themes functions.php file (be sure to replace both instances of portfolio to match the actual names you use):
<?php
add_action("template_redirect", 'your_cust_pt_redir');
function your_cust_pt_redir() {
global $wp;
global $wp_query;
if ($wp->query_vars["post_type"] == "portfolio") { // Change Portfolio to your Post Type
if (have_posts()) {
include(TEMPLATEPATH . '/portfolio.php'); // The Custom Template
die();
} else {
$wp_query->is_404 = true;
}
}
}
?>