How to change this registration message: 'A message with further instructions has been sent to your email address' ?

Incorrect, you are referring to the email message. The original poster is referring to the message within drupal via drupal_set_message():

The offending code is below, resides in modules/user/user.pages.inc, you might be able to user hook_form_alter to grab the submit handler? Not sure off hand. Or just use the awesome string overrides module as suggested above.

function user_pass_submit($form, &$form_state) {
  global $language;

  $account = $form_state['values']['account'];
  // Mail one time login URL and instructions using current language.
  $mail = _user_mail_notify('password_reset', $account, $language);
  if (!empty($mail)) {
    watchdog('user', 'Password reset instructions mailed to %name at %email.', array('%name' => $account->name, '%email' => $account->mail));
    drupal_set_message(t('Further instructions have been sent to your e-mail address.'));
  }

  $form_state['redirect'] = 'user';
  return;
}