Similar issue as for Drupal 4:

http://drupal.org/node/3603

is happening to me with Drupal 6.2, Garland theme and i18n module. Search results lists "Page" and "Story" instead of their translated versions for choosen language. Other like # of comments are fine.

I've created search function in template.php (theme's folder) and tried to put t() wrapper arround possible places in other files where search output is generated but with no success. Any help?