I have just tried your solution on one of my grids with 1100 distinct values. To perform a "Select All" on a column was taking about 1 second (and similar with a unselect All) - I have a SelectAll and CancelAll button on each of the column filter lists.
The select all code is as follows:
DataGridCollectionView view = this.ItemsSource as DataGridCollectionView;
System.Collections.IList distinctValues = view.DistinctValues[sColumnFieldName];
foreach (object value in distinctValues)
My ItemsSource is a DataTable wrapped inside a DataGridCollectionView.
As Jenny said, if you can send them a testapp they shoudl be able to identify what is causing the delay.