Proposed resolution:

Change the declarations of find_first_of to:

template<class ForwardIterator1InputIterator1, class ForwardIterator2>
  ForwardIterator1InputIterator1
  find_first_of(ForwardIterator1InputIterator1 first1, ForwardIterator1InputIterator1 last1,
                        ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1InputIterator1, class ForwardIterator2,
                  class BinaryPredicate>
ForwardIterator1InputIterator1
  find_first_of(ForwardIterator1InputIterator1 first1, ForwardIterator1InputIterator1 last1,
                         ForwardIterator2 first2, ForwardIterator2 last2,
                        BinaryPredicate pred);

In 25.1.4 Find First [lib.alg.find.first], the two iterator type parameters to find_first_of are specified to require Forward Iterators, as follows:

template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1
  find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
                        ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
                  class BinaryPredicate>
ForwardIterator1
  find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
                         ForwardIterator2 first2, ForwardIterator2 last2,
                        BinaryPredicate pred);

However, ForwardIterator1 need not actually be a Forward Iterator; an Input Iterator suffices, because we do not need the multi-pass property of the Forward Iterator or a true reference.