I often get the “NameVirtualHost *:80 has no VirtualHosts” on my webservers. It seems that every version of every distro has different requirements. My existing Debian config was fine, until I upgraded to Lenny. With fiddling, I determined the solution:

In /etc/apache2/ports.conf, put (among other things): 

NameVirtualHost *
Listen 80
 
<IfModule mod_ssl.c>
    # SSL name based virtual hosts are not yet supported, therefore no
    # NameVirtualHost statement here
    Listen 443
</IfModule>

Then you can define virtual hosts: 

<VirtualHost *>
    ServerName bla
    ServerAlias hoho
</VirtualHost>

The key is to not define *:80 for the namevirtualhost and virtual hosts. Instead, use the listen directive to define the port.