Proposed resolution:

This wording is relative to N4800.

1. Change [algorithm.syn] as indicated:

   // [alg.random.shuffle], shuffle
   […]
   namespace ranges {
     template<RandomAccessIterator I, Sentinel<I> S, class Gen>
       requires Permutable<I> &&
                UniformRandomBitGenerator<remove_reference_t<Gen>> &&
                ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<I>>
     I shuffle(I first, S last, Gen&& g);
   
     template<RandomAccessRange R, class Gen>
       requires Permutable<iterator_t<R> &&
                UniformRandomBitGenerator<remove_reference_t<Gen>> &&
                ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<iterator_t<R>>>
     safe_iterator_t<R> shuffle(R&& r, Gen&& g);
   }
   […]
   

[ 2019-06-16 Set to "Tentatively Ready" after five positive votes on the reflector. ]

[ 2019-03-05 Updated proposed wording according to Casey's suggestion ]

[ 2019-03-05 Priority set to 1 after reflector discussion ]

Casey: The correct fix here is to remove the ConvertibleTo requirement from the header synopsis. UniformRandomBitGenerators have integral result types, and the core language guarantees that all integral types are convertible to all other integral types. We don't need to validate the core language in the associated constraints of ranges::shuffle.

Previous resolution [SUPERSEDED]:

This wording is relative to N4800.

1. Change [alg.random.shuffle] as indicated:

   […]
   namespace ranges {
     template<RandomAccessIterator I, Sentinel<I> S, class Gen>
       requires Permutable<I> &&
                UniformRandomBitGenerator<remove_reference_t<Gen>> &&
                ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<I>>
       I shuffle(I first, S last, Gen&& g);
     template<RandomAccessRange R, class Gen>
       requires Permutable<iterator_t<R>> &&
                UniformRandomBitGenerator<remove_reference_t<Gen>> &&
                ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<iterator_t<R>>>
       safe_iterator_t<R> shuffle(R&& r, Gen&& g);
   }
   

[ 2019-03-03; Daniel comments ]

Given that the accepted proposal P0896R4 voted in San Diego did contain the same error I decided to open this issue instead of submitting an editorial change request.

[algorithm.syn] declares std::ranges::shuffle like so:

namespace ranges {
  template<RandomAccessIterator I, Sentinel<I> S, class Gen>
    requires Permutable<I> &&
             UniformRandomBitGenerator<remove_reference_t<Gen>> &&
             ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<I>>
  I shuffle(I first, S last, Gen&& g);

  template<RandomAccessRange R, class Gen>
    requires Permutable<iterator_t<R> &&
             UniformRandomBitGenerator<remove_reference_t<Gen>> &&
             ConvertibleTo<invoke_result_t<Gen&>, iter_difference_t<iterator_t<R>>>
  safe_iterator_t<R> shuffle(R&& r, Gen&& g);
}

[alg.random.shuffle] defines the algorithm like so:

namespace ranges {
  template<RandomAccessIterator I, Sentinel<I> S, class Gen>
    requires Permutable<I> &&
             UniformRandomBitGenerator<remove_reference_t<Gen>>
  I shuffle(I first, S last, Gen&& g);

  template<RandomAccessRange R, class Gen>
    requires Permutable<iterator_t<R>> &&
             UniformRandomBitGenerator<remove_reference_t<Gen>>
  safe_iterator_t<R> shuffle(R&& r, Gen&& g);
}

Notice the missing ConvertibleTo requirements in the latter. Looking at the Ranges TS, [alg.random.shuffle] includes this requirement, albeit in the Ranges TS-format.