How do I change the HTML structure of the primary links in Drupal 7?
It's useful to refer to the API documentation when you have an idea of what to do in version 'X' of Drupal and you want to translate the method to work in version 'Y'.

In this instance, the following API page will prove useful: 

http://api.drupal.org/api/drupal/includes--theme.inc/function/theme_links/7