Can you be more specific? I would like to file a bug, if it hasn't been
done already. I took a brief look earlier this week, and was unsure just
where this was coming from. I can look deeper, of course, but thought
I'd check if you had already tracked it down.
steve@gashuffer:~$ apt-cache show php4
[snip]
Depends: libapache-mod-php4 (>= 4:4.3.10-9) | libapache2-mod-php4 (>= 4:4.3.10-9) | caudium-php4 (>= 4:4.3.10-9), php4-common (>= 4:4.3.10-9)
No bug necessary, you just have to look at the dependencies. So, to
install php4, you either need libapache-mod-php4, libapache2-mod-php4,
or caudium-php4. The fact that apt chose the caudium route probably
meant that it was an easier to satisfy dependency (guesswork - I didn't
delve into that side of it.
Just apt-get install php4 $webserver-php4 to get the right modules.