the problem is that the permalink settings don't affect portfolio permalinks. The only option which has an impact is the "Category base" option.
If you open portfolio.php located in the folder "theme_options" you'll finf following two code lines which are responsible for permalink generation:
$slugRule = get_option('category_base');
if($slugRule == "") $slugRule = 'category';
'rewrite' => array('slug'=>$slugRule.'/portfolio','with_front'=>true),
So if you enter a category base under Setting > Permalink this base will be used instead of the word "category". The second code line appends "/portfolio" to the permalink. So whatever you change under Permalink settings (except category base) doesn't affect your portfolio entries but only your blog posts and pages. I played with the code lines I posted above as well when I looked into your problem but I couldn't solve it eventually.
I hope James can jump in - maybe he knows what's going on.