Open skin1/customer/service_head.tpl, find
Code:
<title>{$html_page_title|escape}</title>
and replace with
Code:
{if $main eq "catalog" && $current_category.category eq ""}
<title>YOUR NEW TITLE HERE</title>
{else}
<title>{$html_page_title|escape}</title>
{/if}