Just had a quick play around with this, I would personally drop the height of the header area, bring the search box into the main focus in the centre, and then look again at the alignment of the logo with the grid below and possibly look to split the header area into 3 even sections, one for identity, one for menu & search and one for contact details.
I think the placement of the search is fine but it looks strange with the 'search' above the form field.
Perhaps you could put the 'Search' text and the magnifying glass inside the search field instead and increase the width of the field so it occupies the same amount of space? Then tone down the gradient, search text and the key line?
Also I'm not sure about the background. It seems a bit too 'grungy' for a jewellery site, although it does give a nice contrast to the cleanliness of the rest of the design. Maybe you could try with a more 'polished' looking texture?
Hope that helps in some way!
EDIT: Greg's post wasn't there when I started writing (I guess Mr. Slow suits me pretty well ). Looks much better like that.