Is WordPress being sofa kingdom by returning Error 404 for custom taxonomies, or doesn't recognize taxonomy-{name}.php template files in your theme? Does it inexplicably start working if you set permalinks to "default"? Can you likewise find very little documentation as to why this might be the case?