As I expect you found, the file should be named boxhead-search.gif instead of headbox-search.gif; it does go into the /includes/templates/cherry_zen/buttons/english/ folder.

Can you give a link to your site? It may be a CSS issue, which I can best resolve by seeing it live.