Here’s an odd one.
We had customized our master pages by adding in the Search WebPart, so we could customize some of the parameters
We changed the following:
<asp:ContentPlaceHolder id="PlaceHolderSearchArea" runat="server"></asp:ContentPlaceHolder>
To the following...