In order to use THEME_menu_tree on the primary menu, instead of using THEME_menu_tree__main_menu(), you will need to use THEME_menu_tree__primary()
This is because the menu that provides the primary links is defined in admin/structure/menu/settings.
I thought of this while digging around in the radix theme's radix_preprocess_page() function, wherein the main menu variable is set up for use in the page.tpl.php by using variable_get(). Duh! It's so easy to forget about those tiny little configurations.
So yeah. THEME_menu_tree__primary() and THEME_menu_tree__secondary() are probably the functions you are looking for!