How to change cleveref references to 'verbal' varioref style?

A nice bug! There is a space character missing in the cleveref package. Line 2337 currently reads:

        \advance\@tempcnta-2%

but should read:

        \advance\@tempcnta-2 %

yes, it is that space character (see What are the differences between TeX counts and LaTeX counters?).

I have notified Toby Cubitt, but for now you can either fix your package source locally, or overwrite the change in your preamble as follows:

\documentclass{report}
\usepackage{varioref}    
\usepackage{cleveref}

\makeatletter
\def\cref@old@@vpageref#1[#2]#3{%
    \leavevmode%\unskip  <<<
    \global\advance\c@vrcnt\@ne%
    \vref@pagenum\@tempa{\the\c@vrcnt @vr}%
    \vref@pagenum\@tempb{\the\c@vrcnt @xvr}%
    %\vref@label{\the\c@vrcnt @xvr}%  <<<
    \ifx\@tempa\@tempb\else%
      \vref@err{\noexpand\vref or \noexpand\vpageref at page boundary
                \@tempb-\@tempa\space (may loop)%
                }%
    \fi%
    \vrefpagenum\thevpagerefnum{#3}%
    \vref@space%
    \ifx\@tempa\thevpagerefnum%
      \def\@tempc{#1}%
      \ifx\@tempc\@empty%
         \unskip%
      \else%
         #1%
      \fi%
    \else%
      #2%
      \is@pos@number\thevpagerefnum%
         {%
          \is@pos@number\@tempa%
           {\@tempcnta\@tempa%
            \advance\@tempcnta\@ne%
           }%
           {\@tempcnta\maxdimen}%
          \ifnum \thevpagerefnum =\@tempcnta%
           \ifodd\@tempcnta%
             \if@twoside%
               \reftextfaceafter%
             \else%
               \reftextafter%
             \fi%
           \else%
             \reftextafter%
           \fi%
          \else%
            \advance\@tempcnta-2 %  <--- there was a space missing here!
            \ifnum \thevpagerefnum =\@tempcnta%
              \ifodd\@tempcnta%
                \reftextbefore%
              \else%
                \if@twoside%
                  \reftextfacebefore%
                \else%
                  \reftextbefore%
                \fi%
              \fi%
            \else%
              \reftextfaraway{#3}%
            \fi%
          \fi%
         }%
         {\reftextfaraway{#3}}%
    \fi%
    \vref@label{\the\c@vrcnt @xvr}%  <<<
    \vref@label{\the\c@vrcnt @vr}%
  }%
\makeatother

\begin{document}

        % This figure appears on page 1.
        \begin{figure}[!htb]
          \centering
          \rule{24pt}{24pt}
          \caption{The famous black square}
          \label{OneBlackSquare}
        \end{figure}

        % This sentence appears on page 2.
        \clearpage
        The non-color black is shown in \vref{OneBlackSquare}.

\end{document}

This gives the expected:

The non-color black is shown in Fig. 1 on the preceding page.