apache-httpd provides httpd (as does cern-httpd) so dpkg won't install one until the other is removed.
This isn't completely optimal (for the people who want to use apache but also need a proxy server). Ideally, someone should write up a mini-howto on how to work around this simplicity feature. -- Raul