Is there a way to programmatically add new links to the primary links?
You can either specifiy the menu name in hook_menu() (look for 'menu_name') if they are defined with that hook or you can use menu_link_save().

Yet another option would be to use http://drupal.org/project/features and export your menu structure as a feature.