I have 4 servers online with CentOS 4.2 and plesk 7.5.4 and they're great! The key is to change /etc/redhat-release to read:
RedHat Enterprise Linux EL4 (Nahant)
I believe Plesk only has an installer for CentOS 3.x, but this method works since the two are basically mirrors of themselves. And it creates no problems with up2date or yum (using ART's anyway)