I ran into the same problem ...
I did following :
dpkg -l | grep apache
and I removed every single package containing apache2 like this :
# apt-get remove xxpackagenameyoufoundxxx
# dpkg --purge xxpackagenameyoufoundxxx
sometimes when you try to run apt-get remove xxxpackagenameyoufoundxxx it wont work cause the packagename does not correspond ...
then you have to do this :
apt-cache search packagename from dpkg -l without the version number, then do an apt-get remove with the package name that corresponds more or less from your dpkg -l ...
if you removed all the apache2 stuff you can do a find / -name apache2 to be sure you removed everything ...
I reinstalled all my packages, reinstalled apache (ver 1.3 !!!!) and php4 ...
keep posted, we'll fix your prob
