I did not really find a way to assign categories to uploads, but I was able to come up with some php code that retrieves attachments that have been added to posts in a given category.
Probably not too elegant, but it works fine for me. Here is the relevant snippet:
$last_posts = (array)$wpdb->get_results("
SELECT DISTINCT P2.ID, P2.post_type,
P2.post_title,
P2.post_date,
{$tp}terms.term_id as post_category,
P2.post_content
FROM {$tp}posts as P1, {$tp}posts as P2, {$tp}terms,
{$tp}term_relationships, {$tp}term_taxonomy
inner join {$tp}posts on P1.ID=P2.post_parent
WHERE {$tp}terms.term_id = {$curr_cat_id}
AND {$tp}posts.ID = {$tp}term_relationships.object_id
AND {$tp}term_relationships.term_taxonomy_id = {$tp}term_taxonomy.term_taxonomy_id
AND {$tp}term_taxonomy.term_id = {$tp}terms.term_id
AND P1.post_status = 'publish' and P2.post_type='attachment'
ORDER BY post_date {$newest_check}
LIMIT 10
");
if (sizeof($last_posts) > 0) {
foreach ($last_posts as $lpost) {
$the_output .= '<li><h6><a href="' . get_permalink($lpost->ID) . '">' . $lpost->post_title . '</a></h6>';
$the_output .= $lpost->post_content;
$the_output .= '</li>';
}