I figured it out! For anyone having the same problem, I solved it by adding
$cat_id = get_query_var('cat');
query_posts("post_type=company&cat=$cat_id");
right in front of the loop. Anyone having the same problem would probably also benefit from looking at this, too.