ToC header appears in next chapter

You can use \frontmatter, \mainmatter and \backmatter commands and place the whole frontmatter inside a "group" (\begingroup and \endgroup commands) with a \pagestyle{plain} command just after \frontmatter:

\documentclass{book}
\usepackage[Conny]{fncychap}%Options: Sonny, Lenny, Glenn, Conny, Rejne, Bjarne, Bjornstrup
\UCTfalse
\usepackage{blindtext}
\title{Test}
\begin{document}


\maketitle
\begingroup
\pagestyle{plain}
\frontmatter
\tableofcontents
\chapter*{Prologue}
\blindtext[5]
\endgroup
\mainmatter
\chapter{Introduction}
\blindtext[5]
\backmatter
\appendix
\chapter{App1}
\blindtext[5]
\end{document}

Check the headers and footers in the result of the above code to see if everything is as expected from you.

suppressing the chapter name with \chapter*{} causes the headers not to update. You can change that by adding \markboth{Prologue}{}.

\documentclass{book}
\usepackage[Conny]{fncychap}%Options: Sonny, Lenny, Glenn, Conny, Rejne, Bjarne, Bjornstrup
\UCTfalse
\usepackage{blindtext}

\begin{document}
    \tableofcontents
    \chapter*{Prologue}
    \addcontentsline{toc}{chapter}{Prologue}  % if you want to add the Prologue to TOC
    \markboth{Prologue}{}                     % to change the header despite \chapter*{} command
    \blindtext[5]
\end{document}

Here's the result:

Hope this helps :)

Edit: note that you will have to do this for every chapter you suppress with *, if you want it to change the headers, not just after the TOC.