I have successfully themed the Spotlight search bar by creating this path inside my theme:

Suave\UIImages\UISearchBarBorder.png

This will replace the Spotlight search bar with my custom one, and it works fine. It also themes some other search bars in applications. It does not, however, theme the one inside the default Phone application in your contact list. Does anyone know where it's pulling the search bar from?

Thanks!