Ein schneller Dirty Fix:
mkdir /etc/apache2/suexec
nano /etc/apache2/suexec/www-data
/var/www
public_html/cgi-bin
# The first two lines contain the suexec document root and the suexec userdir
# suffix. If one of them is disabled by prepending a # character, suexec will
# refuse the corresponding type of request.
# This config file is only used by the apache2-suexec-custom package. See the
# suexec man page included in the package for more details.
Ich kenne das verhalten ebenfalls von Server Umzügen, habe es aber bisher nicht analysiert.
Apache neu starten nicht vergessen.