I’m actually having this issue, too. Since it works otherwise fine EXCEPT for permalink generation, I figured it’s got to be something wrong in the permalink generation, and this is the (hacky) thing I ended up doing (this is WP 3.0):
Go to /wp-includes/link-template.php
Go to the function “get_permalink”. in the array $rewritecode, add another entry of ‘%tag%’ at the very end. You will also have to add a corresponding entry at the end of $rewritereplace. Before that array is declared, I did:
$post_tag_name = get_the_tags($post->ID);
if (!empty($post_tag_name))
{
foreach($post_tag_name as $tag)
{
$post_tag_name = $tag->slug;
break;
}
}
And then at the end of $rewritereplace, I added $post_tag_name.
I presume you can do the same thing for custom taxonomies.
This is pretty hacky, but it works. Ideally, this should be a plugin, but I don’t care enough right now to do it right.