I found the cause of this problem. I noticed that the difference between the domains that Zen installed ok on and those that it didn't was the age of the hosting.

PHP had been rebuilt on the server, those domains that had been hosted since before the rebuild were affected, those created after the rebuild were fine.

To fix the problem, I simply deleted the older hosting, recreated it and installed Zen.

It's still odd that this problem only apears to affect Zen during installation and not while running though. To be on the safe side, I think I'll recreate the hosting and reinstall Zen on all the older stores in case of any future problems.