Add a message to messages array using theme process or preprocess function
$messages isn't an array of messages; it's the rendered output of theme_status_messages(). From the point at which you're looking to add messages (template_process_page()), Drupal has already processed all the messages it's going to render. 

If you're looking to print some debugging messages you can do something like this:

function MYTHEME_process_page(&amp;$variables) {
  drupal_set_message('new test message');

  //This will overwrite any previous messages that were to be rendered
  $variables['messages'] = theme_status_messages(array('display' =&gt; null));
}