Blogs are not being created

I am getting random blogs not created, with the message:
The blog you have requested is not installed properly. Please contact the system administrator.

It tells the user the blog has been created, but when you click on the blog url it will say that. The blog tables are not being added to the database. I am using wpmu 2.6.2 with the 2.6.0 multi-db.

Has anyone had this problem? Its a very serious issue and I cant figure it out because it used to work fine, and logs arent showing me anything about this.