Does this error pop up when you try to repair the data source? Usually those exclamation marks mean Arc can't find the data, typically because either the mxd or the data has been moved to a different location. If that's the case, you can right click a layer and select Data | Repair data source, navigate to where the file is and click on it. This will fix any bad pathed layers in the same path.
Other things you could try - see if you can add the shapefiles to a new map; try opening the .dbf file in Excel or Access. This last might be useful, since the error states 'Database not found'. The dbf file is the only database related file in a shapefile (DBF = DataBase File).
Apologize if you know all this, not sure how knowledgeable in Arc you are.