it isn't in a template, it's in a library.

edit /libs/html.inc.php

PHP Code
$new_flasher =  "<a href=\"" .  make_ubb_url("ubb=viewmessages", "", false) . "\"><img src= \"{$config['BASE_URL']}/images/{$style_array['general']}/newpm.gif\" border=\"0\" alt=\"$lang_string\" title=\"$lang_string\" /></a>";

This line you can find in that file, and you could replace newpm.gif with a new filename.

[Linked Image from siemons.org]