I'll give a couple answers to this and I'm basing it on the Twitter Bootstrap theme because of your comment back to onirio. I had the same issue using the same theme.
If all you want to do is change the class name once (it doesn't sound like it, hence the second answer - stay tuned), then you can visit the function "twitter_bootstrap_preprocess_page" in twitter_bootstrap/template.php. Within there, you will find this construct:
$variables['primary_nav'] = theme('twitter_bootstrap_links', array(
'links' => $variables['main_menu'],
'attributes' => array(
'id' => 'main-menu',
'class' => array('nav'),
Simply, change the 'nav' to be whatever you want it to be. That will change it everywhere. Better would be to do as I did and sub-theme and change that rather than the actual Twitter Bootstrap theme.
If you want to do something more interesting, then consider instead where the aforementioned code is used. It is used in the function "twitter_bootstrap_twitter_bootstrap_links" found within includes/modules/theme.inc. You will see that function using these variables as such:
links = $variables['links'];
$attributes = $variables['attributes'];
$output .= '<ul' . drupal_attributes($attributes) . '>';
So, if you want to get more fancy, then you'll need to modify the way that the ul is built. That may be served through researching or posting another more targeted question? Again, doing this in a sub-theme would be best.