This message appears when a SharePoint list gets large (>5000 items). The default list view threshold for any SharePoint list is 5000. Once this threshold is crossed the list becomes slow and many features of the list does not work.
The only work around you can do now is to increase the threshold. This can be done at web application level in central administration. See this post on increasing list view threshold.
While the damage has already been done, it is not a good approach to increase the list view threshold. SharePoint can support around 30,000,000 items in each list.But in a single view it can support only 5000 items by default. It is always to prepare and plan in advance for the large lists. See this blog on designing large lists in SharePoint.