Edit account creation message
This is exactly what the String Overrides module is for.

If you only need just a couple strings, you can also use settings.php.  See this section:

/**
 * String overrides:
 *
 * To override specific strings on your site with or without enabling locale
 * module, add an entry to this list. This functionality allows you to change
 * a small number of your site's default English language interface strings.
 *
 * Remove the leading hash signs to enable.
 */


You don't want to use Rules, because although you can add a new message with a rule, the old message will still be there as well (which isn't what you want, I assume).