The problem is that you cannot choose a domain and codomain for such a putative adjunction consistently and simultaneously. The statement that we have is that the category of presheaves on $C$ is the free cocomplete category on $C$ when $C$ is small. However, the forgetful functor from cocomplete categories to categories does not land in small categories-every cocomplete category which is not a preorder is large.
So, you might want an improved adjunction between large categories and cocomplete categories. However, the category of presheaves on a large category is even larger than large! What this means depends on your foundations. If we work with universes so that a small category is $U_1$-small, then presheaves on a small category are small with respect to the next biggest universe $U_2$. Now presheaves on a $U_2$-small category only have the appropriate universal property if we can them to be presheaves of $U_2$-small sets, and such presheaves are not $U_2$-small.
So the presheaves-forgetful functor pair cannot form an adjunction, because the desired left adjoint moves us up a universe every time we apply it. Thus in particular we cannot get around this straightforwardly by using universes.
There are a couple of partial solutions to this problem. The simplest is to regard the formation of the presheaf category as a relative left adjoint to the forgetful functor from cocomplete categories to (possibly) large categories. In other words, it behaves like a left adjoint, but is only partially defined. This is a rephrasing of the theorem you quote-the formation of presheaves behaves like a left adjoint when its input is small.
A more technical approach is to ask the question: even if the formation of presheaves cannot be left adjoint to the forgetful functor from cocomplete categories to large categories, does this forgetful functor have any left adjoint at all? In fact it does; for instance, it satisfies a 2-categorical version of the general adjoint functor theorem. This left adjoint sends a category $K$ to the subcategory of presheaves on $K$ formed by the colimits of small diagrams of representable presheaves. However, this category of small presheaves is not nearly as well behaved as the presheaf category. It needn't even be a topos in general.
So to summarize, this is a real issue which cannot be eradicated by any level of generous assumptions on the foundations. It's the go-to example of why size issues cannot be completely ignored in category theory.