Using Satellite search is encountering "Index files missing from search-server" error

Issue

• Encountering this error when using the Satellite search function: "Index files missing from search-server. Assuming data exists in database, indexes can be regenerated by running: /usr/sbin/rhn-search cleanindex,
  then restart rhn-search".
• We clean the index as instructed, but the problem comes back after the indexes have been created.
• We are using a Satellite 5.6 system with the latest packages described in RHBA-2013:1827 but the error is still occurring.