I have already tried doing this in theme_preprocess_page() in template.php and this works if I output the array to the browser but the menu itself remains unchanged.
I have also tried using hook_menu_alter() but again this does not change the primary links.
Where am I going wrong here?