The user guide to the fancyhdr package notes on p. 10 that
It should be noted that the LATEX marking mechanism works fine with chapters (which always start on a new page) and sections which are reasonably long. It does not work quite as well with short sections and subsections. This is a problem with LATEX, not with fancyhdr.
AFAICT, an easy workaround, which doesn't require the redefinition of LaTeX's \tableofcontents command, consists of specifying \rhead{} before the \tableofcontents command, followed by \rhead{\rightmark} before the first section:
\documentclass[12pt]{article}
\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{\leftmark}
\begin{document}
\rhead{} % set \rhead to empty
\tableofcontents
\clearpage % OP has indicated that ToC spans a full page
\rhead{\rightmark} % reset \rhead to \rightmark
\section{Hello}
\end{document}
\sectioncommand in the same page of your ToC, the problem disappears. – Gonzalo Medina Mar 18 '12 at 00:04