I have it running on 3.6.8 PL2 with no issues (but it is in the navbar, not the header). Another option is to put the template code in there manually.
Where the $google_navadsearch is in your header, take that out and put in this
Code:
<tr>
<form method="get" action="{$vboptions['google_forum_path']}" target="_top"><td class="thead">Search Site / Google</td>
</tr>
<tr>
<td class="vbmenu_option" title="nohilite">
<table border="0">
<tr>
<td nowrap="nowrap">
<input type="hidden" name="domains" value="{$vboptions['homeurl']}"></input>
<input type="text" name="q" size="31" maxlength="255" value=""></input>
<input type="submit" name="sa" value="Go"></input>
</td>
</tr>
<tr>
<td nowrap="nowrap">
<table border="0">
<tr>
<td>
<input type="radio" name="sitesearch" value="" id="ss0"></input>
<label for="ss0" title="Search the Web">{$vboptions['google_label_web']}</label>
</td>
<td>
<input type="radio" name="sitesearch" value="{$vboptions['homeurl']}" checked id="ss1"></input>
<label for="ss1" title="Search {$vboptions['homeurl']}">{$vboptions['google_label_site']}</label>
</td>
</tr>
</table>
<input type="hidden" name="client" value="{$vboptions['google_pub']}"></input>
<input type="hidden" name="forid" value="1"></input>
<input type="hidden" name="ie" value="ISO-8859-1"></input>
<input type="hidden" name="oe" value="ISO-8859-1"></input>
<input type="hidden" name="cof" value="{$vboptions['google_cof']}"></input>
<input type="hidden" name="hl" value="en"></input>
</td>
</tr>
</table>
</td></form>
</tr>
and make changes where are necessary.