I have exactly the same problem, just started on a couple of boxes that have been running for several months. They are both test VMs, so have re-images both with both previously working images, and fresh Ubuntu and Centos installs followed by a clean Plesk installation. Same problem on all.
Can anyone shed any light?