Error when using Search in Explorer

We are currently on BWA 7.20 Revision 17, BW 7.3 SP3, and BusinessObjects Explorer 4.0 SP2. We recently started experiencing problems with the search functionality in Explorer. The users can still navigate through the information space, create filters and charts. However, when they attempt to use the search while navigating through the Information Space they will receive the below error....

Failed to retrieve a new chart from the server.

It is not possible to generate the chart. (PS 50002).

2007:Index does not exist;index=_trexlib:4ff187b7a422568be1000000c0a8c4f1_index,scripted search: function 'ps_others.search'.

We haven't experienced this error before so obviously we are thinking it has something to do with the connection or the data contained in the index itself. We've tried re-indexing the snapshot index, re-indexing the infospace, rebooting the Explorer servers in the CMC and we even shutdown and restarted one of the blades...all to no avail. Anyone have any ideas as to what might be going on?

Thank you.

Josh Dunlap