This maybe (or not) related to RT-15299. It differs from the test case there in having a custom observableList implementation with minimal (though valid, as per Change doc) change notification, read: no fake removes/adds. Created this as new issue to show a use-case the sortedList must handle gracefully

    /**
     * Implementation of ObservableList for testing removeAll. 
     * NOTE: no other modification operation is supported!
     */
    private static class RemoveAll<E> extends ArrayList<E> implements ObservableList<E> {

        ListenerList<ListChangeListener<? super E>> observers = 
            new ListenerList<ListChangeListener<? super E>>();
        
        public RemoveAll(E... elements) {
            super(Arrays.asList(elements));
        }
        
        /** 
         * @inherited <p>
         */
        @Override
        public boolean removeAll(Collection<?> c) {
            int firstRemoved = findFirst(c);
            super.removeAll(c);
            fireRemoved(firstRemoved, c);
            return true;
        }

        private void fireRemoved(final int firstRemoved, final Collection<?> c) {
            Change change = new Change(this) {
                List removedItems = Collections.unmodifiableList(new ArrayList(c));
                @Override
                public int getFrom() {
                    return firstRemoved;
                }

                @Override
                public int getTo() {
                    return getFrom();
                }
                
                @Override
                public List<E> getRemoved() {
                    return removedItems;
                }

                @Override
                public boolean wasPermutated() {
                    return false;
                }

            };
            for (ListChangeListener listener : observers) {
                listener.onChanged(change);
            }
        }

        private int findFirst(Collection<?> c) {
            int first = size();
            for (Object object : c) {
                // assuming all contained
                first = Math.min(first, indexOf(object));
            }
            return first;
        }

        @Override
        public void addListener(ListChangeListener<? super E> listener) {
            observers.add(listener);
        }

        @Override
        public void removeListener(ListChangeListener<? super E> listener) {
            observers.remove(listener);
        }
        
        @Override
        public boolean addAll(E... elements) {
            throw new UnsupportedOperationException("not interested");
        }

        @Override
        public boolean setAll(E... elements) {
            throw new UnsupportedOperationException("not interested");
        }

        @Override
        public boolean setAll(Collection<? extends E> col) {
            throw new UnsupportedOperationException("not interested");
        }
        
    }
    
    /**
     * Test effect on sorted list (cant cope)
     */
    @Test
    public void testRemoveAllWithSortedList() {
        RemoveAll<Integer> list = new RemoveAll<Integer>(
                0, 1, 2, 3, 4, 5, 6, 7, 8, 9
        );
        SortedList sorted = new SortedList(list);
        List<Integer> removed = Arrays.asList(7, 2);
        list.removeAll(removed);
    }