You need to implement your function earlier than you are. It seems that the “real” wp_new_user_notification() (from wp-includes/pluggable.php) is getting created before yours is. To test, remove the if ( ! function_exists( 'wp_new_user_notification' ) ) :
from your code. You should be getting an error.
You could create a plugin:
//Plugin Name: blahblah
function wp_new_user_notification() {
// your code
}
Alternatively, just put that code in it’s own .php file and drop it in wp-content/mu-plugins directory (create if it doesn’t exist). Problem should be solved.