I found the fix for this problem.
You need to add the line "NameVirtualHost *:80" into /etc/apache2/httpd.conf. This seems to be very important because if it's not there then the first vhost will be treated weird. Here is the link with the fix:
And here are some links describing the problem of no matter which vhost they try to visit, they only can see the first vhost:
Now that it is documented.