Ignore ALL of the advice about setting ServerNames. IMHO this is a red herring. Apache is trying to use standard system components to determine a FQDN and not finding anything suitable. Sure, you could subvert this process by adding a directive globally to Apache, but methinks this is treating the symptom. You should have ServerName directives in your virtualhost blocks, of course.
Instead, edit your hosts file and be sure that you have a FQDN listed there. I have seen various suggestions on the syntax for the particular 127* line, but I think that it doesn't matter what order things are in, so long as there is a FQDN listed:
127.0.0.1 localhost.localdomain localhost foo.example.com
This worked for me and seemed much more to the point than all of the other "worked for me!" upvotes on posts recommending you edit httpd.conf and such. I hope this helps and that I don't get downvoted. If you disagree, please state why with examples. Thanks.
http://wiki.apache.org/httpd/CouldNotDetermineServerName
Once Apache can determine the system's FQDN, it will then read your specific ServerName directives for your NameBasedHosts.