"First argument is expected to be a valid callback" errors on a fresh 6.14 installation

I've just installed Drupal 6.14 on a new host. The installation itself went ok. However I'm getting various errors which seem to be related.

When clicking on Add new content I get the error:
warning: call_user_func_array() [function.call-user-func-array]: First argument is expected to be a valid callback, 'theme_filter_tips' was given in /var/www/httpdocs/includes/theme.inc on line 617.

When performing a search, I just get a white screen (WSOD) and the following error is logged:
warning: call_user_func_array() [function.call-user-func-array]: First argument is expected to be a valid callback, 'search_view' was given in /var/www/httpdocs/includes/menu.inc on line 348.

This is on a completely new Drupal installation, the only modifications I've made were to enable the search module. I don't encounter these problems on either my local machine or on another host I've tried.

Drupal's status report page doesn't indicate any problems. The host is running PHP 5.2.9 and MySQL 5.0.77.

I am inclined to believe it is a PHP configuration problem, but I can't imagine which PHP configuration setting would cause the above errors.

Any advice on what I can try next?

(I actually came across these errors when trying to migrate an existing installation to the new hosts, but after a process of elimination I discovered that a new installation has the same problems).