Search only works for user number 1 - Help!

I have pored over every forum post I can find about problems with the search module and none of them match what I am experiencing, which is:

- The search block will not display in either column for any user except me (user #1 in the users table).
- The search box will display in the header for other users, but returns an access denied page for any one but me.

I have double- and triple-checked everything I can think of, including:

- Access control: every role has "search content" enabled; I even tried giving every role "administer search" privileges too, but that didn't help.
- The search block is enabled for my theme, and is set to "Users cannot control..." and "Show on every page..."
- Indexing status is at 100%; I can search and get good results, but no one else can.

Someone please tell me, what is wrong with search on my site? -- http://texasweekly.com

Doug