The List View Threshold applies when a List query attempts to retrieve a number of items greater than the Threshold. If you're receiving an error, that's the most likely cause.
Some things to check:
Sorting: You cannot apply a sort using a column that is not indexed. If you have sorting applied to the views, ensure you're using only indexed columns.
Item Limit: If no filters are applied and you select "Display items in batches", the query will fail. On the other hand, you can use "Limit the total number of items" selection to satisfy the threshold.
Filters: The columns you select for filtering must also be indexed, and you're limited to using 'AND' for multiple filters; 'OR' will retrieve all items before filters are applied.
I did some quick testing on the filters and it seems pretty inconsistent. I have a list with a number field and applied a filter to get values over 20000 (0 items) OR items less than 5000 (<5000 items). That query failed. However when I did greater than 15000 OR less than 100, I get items in the 5000 range, which makes no sense at all.
If you're not using sorting or it's configured correctly, I'll bet dollars to Timbits it's your filtering. I'm not sure exactly how things have changed from 2010 to 2013, but I know the 2013 List View Threshold is extremely rigid so I suggest you start there.