Internet Explorer is incompatable with some CSS selectors

The multiple classes in IE is buggy, but not that bad.
If you really think you need different XHTML, please use the theme functions.

I'm fairly new to CSS - can you suggest a way that wouldn't have this problem? ie as cross-browser compatible as possible?

Think you already solved this,
but i went into it now and i'm posting the easiest way to fix this problem.
You may add this snippet into your template.php, it simply removes the class tagadelic and you will have tags with class levelx only.
See you
Da.

function  yourtheme_tagadelic_weighted($terms) {
  foreach ($terms as $term) {
    $output .= l($term->name, taxonomy_term_path($term), array('class'=>" level$term->weight")) ." \n";
  }
  return $output;
}

you can still simply refer to it as level-1. Just that -in some situations- tagadelic.level-1 won't work.
PLease read this great article on multiple classes in IE6, and stop the FUD about unsupported multiple tags in IE. It works. Just not very well. But it won't break your site like border-box-models, float-bugs, guillotine bugs, png-transparency and the likes do.

function yourtheme_tagadelic_weighted($terms) {
foreach ($terms as $term) {
$output .= l($term->name, taxonomy_term_path($term), array('class'=>" level$term->weight")) ." \n";
}
return $output;
}

Tried this solution but the classes weight in ie6 appears the same. :-S

Tag clouds with the same weight are not so cool as tags with different sizes!

Any help?

I agree.
I tried the code suggested.
No change in IE

Oddly enough, I don't see another page about this problem. No one has complained about in Drupal 6 that I could find.