It sounds like maybe your cluster is too busy and so it isn't able to create the primary shard before the timeout. Perhaps there is another reason, which should be in the logs.
If you were on Elasticsearch 5, you could use the cluster-allocation-explain API to get an easy explanation for what is going wrong.