Error: 'Invalid Report. You cannot run this report because its formulas or filters are invalid'

This occurs because one of the fields used in the Report filter criteria is not visible to the Running User due to Field Level Security.
 

Without the use of filter logic (e.g. (1 AND (2 OR 3) AND 4) in the Report, the filter is simply removed from the report.

When filter logic is added to the report, the report will attempt to evaluate the number of filters indicated in the filter logic.

However, because the running user does not have visibility to one of the fields in the filter criteria, the report will show less filters than indicated in the filter logic. This variance causes the "Invalid Report" error.
 

To troubleshoot, review the field accessibility for all fields used in the filter criteria of the report. 
Go through each of the fields in the filter criteria to determine which field is not visible to the Affected User's Profile.

Additionally, this may occur for users within the Partner or Customer portal if the amount of filters exceed 10.
These portal licenses only permit access to reports with a maximum of 10 filter criteria even though the Report Builder permits up to 20 filters for internal users.

This error message may also occur if a Platform user has been assigned a profile that lacks the "Create and Customize Reports" permission. Lacking this option prohibits reports from being run with more than 10 lines of filter criteria.