1 of 3

This happens because the links are only the titles of entries in the ToC. The page numbers themselves are not hyperlinked. To have these also coloured similarly to the hyperlink colours, you could patch \l@chapter (the macro responsible for typesetting the chapter-style ToC entries) and \@dottedtocline (the macro responsible for typesetting other non-chapter-style ToC entries):

enter image description here

\documentclass{book}
\usepackage{etoolbox,hyperref,xcolor}% http://ctan.org/pkg/{etoolbox,hyperref,xcolor}
\definecolor{wine-stain}{rgb}{0.5,0,0}
\hypersetup{
  colorlinks,
  linkcolor=wine-stain
}
\makeatletter
% \patchcmd{<cmd>}{<search>}{<replace>}{<success>}{<failure>}
\patchcmd{\l@chapter}{\hss}{\color{wine-stain}\hss}{}{}% Chapters in ToC
\patchcmd{\@dottedtocline}{\normalcolor}{\color{wine-stain}}{}{}% Other sections in ToC
\begin{document}
\tableofcontents

\chapter{First chapter}
\section{First section}
\subsection{First subsection}
\subsubsection{First subsubsection}
\subsubsection{Second subsubsection}
\subsection{Second subsection}
\subsubsection{First subsubsection}
\subsubsection{Second subsubsection}

\section{Second section}
\subsection*{An unnumbered first subsection}
\subsubsection{First subsubsection}
\subsubsection{Second subsubsection}
\subsection*{An unnumbered second subsection}
\subsubsection{First subsubsection}
\subsubsection{Second subsubsection}

\chapter{Second chapter}
\section{First section}
\subsection*{An unnumbered first subsection}
\subsubsection{First subsubsection}
\subsubsection{Second subsubsection}
\subsection*{An unnumbered second subsection}
\subsubsection{First subsubsection}
\subsubsection{Second subsubsection}

\section{Second section}
\subsection{First subsection}
\subsubsection{First subsubsection}
\subsubsection{Second subsubsection}
\subsection{Second subsection}
\subsubsection{First subsubsection}
\subsubsection{Second subsubsection}

\end{document}

Adding linktocpage is not sufficient, since the sectional units are then not hyperlinked.