In page.tpl.php you have an IF statement which determine whether the Search region is populated or not and then sets a class on the Primary Links to define the proper width. I have rewritten it to make it easier to read and maintain. If you like it, then please integrate. I'm intending to create additional conditional logic using the new pattern provided below.
Existing code - current you are using IF...ELSE...
<div id="primary-left" <?php if ($search): print 'class="withsearch"';
else: print 'class="withoutsearch"';
Recommend code - the following produces the same results but with to optimizations
1. the word 'class' is outside of the php so I only need it once
2. the ternary operator (eval ? true : false) makes the code more concise
<div id="primary-left" class="<?php print $search ? 'withsearch' : 'withoutsearch'; ?>">