Custom taxonomy URLs

I’m having some trouble with custom taxonomies. Here’s the code I use to register them:

register_taxonomy('problem_type', 'attachment', array(
    'hierarchical' => false,
    'label' => __('Problem Type'),
    'query_var' => 'problem_type',
    'rewrite' => array('slug' => 'problem-type'),
    ));
register_taxonomy('problem_difficulty', 'attachment', array(
    'hierarchical' => false,
    'label' => __('Problem Difficulty'),
    'query_var' => 'problem_difficulty',
    'rewrite' => array('slug' => 'problem-difficulty'),
    ));

Then I use this code to print a list of them so I could browse through matching objects:

<?php wp_tag_cloud(array('taxonomy' => 'problem_type', 'format' => 'list')); ?>
    <?php wp_tag_cloud(array('taxonomy' => 'problem_difficulty', 'format' => 'list')); ?>

I do get a list, but the link is something like “http://www.sitename.org/?problem_type=foo” instead of the nice URL I expected like “http://www.sitename.org/problem-type/foo/”. Also the URL doesn’t work at all. It just my site’s homepage; the posts aren’t even filtered or anything.

a) How do I get URL rewriting working with custom taxonomies?
b) How do I actually get a list of matching objects?
c) Is it OK that I’m using them for attachments or is that broken?

Now I realize it’s a bit unusual that I’m using taxonomies on attachments, but I tried to use them on posts just to test out and had the identical problem.