Both core phptemplate themes use name="keys" instead of name="edit[keys]", which was introduced since 4.6.
This would cause the search box not to work.
The attached patch fixes this.
Committed to HEAD. Thanks.
Drupal is a registered trademark of Dries Buytaert.