I recently updated my header to be a full width image, and when I did so the Search box suddenly disappeared.

Can anyone tell me how I can get the Search box back please? My site url is shackn.com

What version of Atahualpa and WP?
What do you have set at ATO->Style & edit HEADER AREA->Show search box?

I have the show search box set to "Yes", and am using version 3.4.1

You need to use %logo in ATO->Style & edit HEADER AREA->Configure Header Area

%logo - The logo area, including the logo icon, the blog title & description, the search box and the RSS/Email icons

Of course! That worked ( you can see the results here... shackn.com)

Another question - can I overlay the search bar over the top of the header image?

try this, you will want to adjust the numbers till you like the results

div.searchbox {position:relative; top:100px; left:-20px;z-index: 4;}