Verifying Hamiltonian Cycle solution in O(n^2), n is the length of the encoding of G
The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this?

First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has an encoding of size $V^2$. However, if an adjacency list encoding is used, we would only need an encoding of size $O(E \log V + V)$.

Your algorithm does indeed run in $O(n)$ time for a dense graph (with $\sim V^2$ edges); does it also run in $O(n)$ time if the graph is sparse ($O(V)$ edges)? In that case, the encoding might be shorter (if an adjacency matrix is used). Is your algorithm still $O(n)$ in that case? If it enumerates over all potential edges or creates and adjacency matrix, it would not be.

CLRS wants to avoid peculiarities with having to implement the algorithm in a particular way or having to specify a specific encoding, which is why they state "you could certainly implement this algorithm to run in $O(n^2)$ time". The "certainly" means "in any case, you can get $O(n^2)$, but it might be possible to do better". In any case, all they care about is that it is polynomial, which both $O(n)$ and $O(n^2)$ are.