You can use \lcnamecref:
\documentclass{article}
\usepackage{ntheorem}
\usepackage[capitalize]{cleveref}
\newtheorem{conjecture}{Conjecture}
\newtheorem{solution}{Solution}
\Crefname{conjecture}{Conjecture}{Conjectures}
\Crefname{solution}{Solution}{Solutions}
\begin{document}
\begin{conjecture} \label{c1} Something happened.
\end{conjecture}
\begin{conjecture} \label{c2} Something else also happened.
\end{conjecture}
\begin{solution} \label{s} A lot of things happened.
\end{solution}
\cref{c1,c2,s} are both \lcnamecref{s} and \lcnamecref{c1}.
\end{document}
The underlying problem has little to do with cleveref in this case. What happens is that calling \frontmatter in aucklandthesis.cls messes up memoir's setup for secnumdepth and, hence, all of your sectioning commands are unnumbered. Therefore, in the MWE at least, \refstepcounter is never called, and your labels miss the information cleveref complains about. If you remove the calls to \cref your document compiles, but with all chapters unnumbered.
The documentclass appears to assume \frontmatter is not to be used at all, since it calls \mainmatter straight from de definition of \maketitle...
It is true that aucklandthesis.cls does not redefine \frontmatter, but it does redefine \mainmatter and, in so doing, leaves out important things of the memoir original. As far as I can tell, you can get things working doing by hand what the class does not do:
\mainmatter
\makeatletter
\@mainmattertrue
\makeatother
\setcounter{secnumdepth}{\value{maxsecnumdepth}}
\pagenumbering{arabic}
But, in this case, it appears this documentclass is not really official to your institution, which means you are not required to use it. In which case you might be better off simply starting from one of the standard classes, memoir itself, or KOMA-Script.
Unfortunately, the original author of the class seems to be long gone from my institution, so I can't ask them about it, and there doesn't seem to be anyone else responsible for maintaining it these days.
Formally, it is a package published on CTAN. Whether its maintainer is still on the institution or not does not change their role wrt to CTAN. Well, that in theory, in practice things might be different... And I did check the documentation and it seems there is no contact information for you to attempt to report this. If you really think sticking to the document class is worth it, you might want to try some contact through CTAN itself. Or, if your institution does advertise this document class as something "official", even if not "required" but just "recommended", you probably should report this to someone at the University.
Best Answer
You need to tell
cleverefhow you want to refer to the algorithms. Something like: