Hello Roman,
I assume you tried downloading the package through HTTP. There is an info link next to the download, md5 and APT links on the download page, that links here: http://pd.ianagnostopoulos.postgrad.shef.ac.uk/notes.txt
This describes the dependencies, and gives you another link, http://pd.ianagnostopoulos.postgrad.shef.ac.uk/pd-deps.tar which contains a tar archive with the three packages of the dependencies.
If you try getting it through the OtherSide APT, the dependencies are there and thus automatically configured.
These three packages have been removed from the official Ubuntu (and I think also Debian) repositories since no package there depended on them. My understanding is that they are NOT replaced by the ones you mentioned. I tried simply changing the dependencies to the newer versions and it installed, but came up with many errors when launching PD.
GEM seems to need the specific versions it depends on. I think that since there is no "serious" reason not to use these libraries, it doesn't make sense doing anything to the source code to make it compatible with the newer versions. If we simply provide these extra packages with the PD package, by hosting them on the same places, it will be fine. Since nothing else has anything to do with them, they won't break anything.
-Ilias