Large list limit on connected web parts

I have a page on SharePoint 2010 with connected web parts. Web part A filters content in a web part B based on column X. Today somebody added an item number 5001 in the list displayed in web part B and the following (obvious) message is now displayed:

This view cannot be displayed because it exceeds the list view threshold (5000 items) enforced by the administrator.

To view items, try selecting another view or creating a new view. If you do not have sufficient permissions to create views for this list, ask your administrator to modify the view so that it conforms to the list view threshold.

Learn about creating views for large lists.

Column X is indexed and I was hoping that after selecting an item in web part A filtered items in web part B will be displayed. Unfortunately I still have that error.

What are my options here to make this work? My requirement is to display all related items in a web part B once an item in A is selected (it is usually less than 100).