Without seeing your markup and css (post a link ;) all I can do is go by the demo for that theme.
The menu is in a div that is approximately 2/3 width of the header and the search is in it's own div floated to the right for the remaining 1/3. So what is probably happening is that you removed the search form but not the containing div. And even if you did you would still need to change the width of the menu div.
This is the selector for the menu container on line 123 of style.css in the demo:
And this is the selector for the search container on line 118:
Just change #search-wrapper to
display: none OR delete that declaration and the container from the template altogether. And then remove the width from the #page-bar (or set it to 'auto' or 100%).
Oh, and I would also remove the float from the menu just so you don't have other mysterious problems later. Remove
class="left clearfloat" from the #page-bar in your templates e.g.
<div id="page-bar" class="left clearfloat">
That should fix your problem.