Headers already sent error when Searching (but not always)

Hey folks,

I’m getting the follow error on my site (http://starfishcoffee.com/):

Warning: Cannot modify header information – headers already sent by (output started at /home/starfish/public_html/index.php:3) in /home/starfish/public_html/wp-blog-header.php on line 529

but only when I search with certain words.

Words that trip it: rumsfeld, armor, whopper
Words that don’t: donald, wake, tsunami
(Thought it might be length, but that doesn’t seem to be it)

Clipped the only extra spacing from wp-config that I could find, but it was still a no go. Recently upgraded to 1.2.2.

Any help would be appreciated!