I cannot install neither Leopard nor Snow Leopard to my virtual machine. It stops with this error:
An invalid Mac OS version is installed. Mac OS X virtual machines can have only the Mac OS X Server Leopard or Mac OS X Server Snow Leopard operating system installed. Other versions of Mac OS are not supported.
I have checked System Requirements for my version of Parallels Desktop and it says that those operating systems are supported as guest OSes. What am I doing wrong?
Neither Leopard nor Snow Leopard are supported to be run on Parallels Desktop virtual machines. That is due to the fact that it is prohibited by Apple's EULA.
You may have misread the system requirements for Parallels Desktop.
For instance, if we look at Parallels Desktop 9 System Requirements, we can see that among non-server Mac operating systems only Lion and Mountain Lion can be installed as guest OS. Note the Server words in the below list: