We prove that the homomorphic quasiorder of finite k-labeled forests has undecidable elementary theory for k ≥ 3, in contrast to the known decidability result for k = 2. We establish also undecidablity (again for every k ≥ 3) of elementary theories of two other relevant structures: the homomorphic quasiorder of finite k-labeled trees, and of finite k-labeled trees with a fixed label of the root element. © Springer-Verlag Berlin Heidelberg 2006.