Thread synchronization wait/notify
Concurrent programming adds a lot of complexity only by the fact that it is concurrent - this alone is reason enough to use concurrency API. One of the rules of good programming is to not reinvent a wheel - which means 

always use available libraries instead of coding yourself unless you have a very good reason to do it

This applies above all to JDK, in your case to the java.util.concurrent package.

Here is a very simple solution, which is so simple only because of concurrent package in JDK - it uses lambda expression so you'll need Java 8, but it's easy to replace is with a Runnable:

import java.util.Random;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ThreadStartTest {

  public static void main(String[] args) {
    int count = 5;

    CountDownLatch latch = new CountDownLatch(count);
    CyclicBarrier barrier = new CyclicBarrier(count);
    ExecutorService pool = Executors.newFixedThreadPool(count);

    Random random = new Random();
    for (int i = 0; i &lt; count; i++) {
      pool.execute(() -&gt; {
        try {
          System.out.println("Thread starts");
          // startup
          Thread.sleep(random.nextInt(100));
          // wait for other threads
          System.out.println("Thread waits");
          barrier.await();
          // process whaterver should be processed
          System.out.println("Thread works");
          Thread.sleep(random.nextInt(1000));
          System.out.println("Thread finished");
        } catch (Exception e) {
          System.err.println("Worker thread inrerrupted");
        } finally {
          latch.countDown();
        }
      });
    }

    try {
      // wait for the threads to be done
      latch.await();
      System.out.println("== End == ");
    } catch (InterruptedException e) {
      System.err.println("Starting inrerrupted");
    }
    pool.shutdown();
  }

}


It does all you need without the need to cope with complex lock/notify sequences with possible deadlocks - just using what the language offers.

If you increase the number of threads you'll notice how the threads start to wait before all even got started, yet all wait for other before starting processing.

Explanation

First let me stress that the concurrent package has very powerful asynchronous concepts that make concurrent programming almost easy :-), so I would suggest trying to get familiar with it and refrain from complex and hard to debug state machines with lock/notify.

Now here we have some constructs from the java.util.concurrent package playing together:

ExecutorService
CyclicBarrier
CountDownLatch


Simple speaking the ExecutorService manages a pool of threads and distributes work between them – it is not guaranteed that each work unit gets a new thread though. Anyway it frees you from creating threads on your own, additionaly you can not only execute Runnable without a return value but also Callable instances, where you can get a return value using Futures. This is powerful, istn't it - submit code to be executed asynchronously and retrieve the result at some time in the future - all that in a very short and simple and expressive code.

In this case the ExecutorService gets created with Executors.newFixedThreadPool(count), so we have exactly the same number of threads as work units, which is important - more about it later.

From Javadoc: 


  CyclicBarrier is a synchronization aid that allows a set of threads to
  all wait for each other to reach a common barrier point.
  CyclicBarriers are useful in programs involving a fixed sized party of
  threads that must occasionally wait for each other.


This is exactly the case here – you wish that all your threads wait for each other before continuing. The parameter to the constructor defines how many threads should wait – in this case exactly the same value as the number of started threads, so each of the threads waits for the count threads get to to that point by calling barrier.await(). After calling the barrier.await() count times the barrier and thus all the threads are released and can continue. 

The CyclicBarrier can be reused, this is why it is called “Cyclic” – just call reset() and you can repeat the whole operation.

Again from the JavaDoc: 


  CountDownLatch is a synchronization aid that allows one or more
  threads to wait until a set of operations being performed in other
  threads completes.


In this case the main thread waits in latch.await until all the threads finish the work and let the latch’s counter get down to zero by calling latch.countDown().

Actually we could make a version without the CountDownLatch – which is then even simpler and uses the ExecutorService awaitTermination method – here the ExecutorService waits until all its threads are finished, so that they do not need the latch. The one drawback of this strategy is that we have to actively cope with timeouts, since the awaitTermination method requires a timeout parameter:

Version without CountDownLatch

public static void main(String[] args) {
  int count = 50;

  CyclicBarrier barrier = new CyclicBarrier(count);
  ExecutorService pool = Executors.newFixedThreadPool(count);

  Random random = new Random();
  for (int i = 0; i &lt; count; i++) {
    pool.execute(() -&gt; {
      try {
        System.out.println("Thread starts");
        // startup
        Thread.sleep(random.nextInt(10));
        // wait for other threads
        System.out.println("Thread waits");
        barrier.await();
        // process whaterver should be processed
        System.out.println("Thread works");
        Thread.sleep(random.nextInt(1000));
        System.out.println("Thread finished");
      } catch (Exception e) {
        System.err.println("Worker thread inrerrupted");
      }
    });
  }

  pool.shutdown();
  try {
    // wait 1 minute for the threads to be done
    pool.awaitTermination(1, TimeUnit.MINUTES);
    System.out.println("== End == ");
  } catch (InterruptedException e) {
    System.err.println("Starting inrerrupted");
  }
}


Now this solution has its own disadvantage: if the thread pool's size is smaller than the number of threads it will dead lock in barrier.await(), because all running threads are waiting for more to come yet no more threads can get executed since the pool has no more available threads. You can try it yourself:

ExecutorService pool = Executors.newFixedThreadPool(count - 1);


And it hangs!

Now I have a 3rd version for you, which doesn’t deadlock – to remove the factor limiting the number of threads I’ll give on ExecutorService up and create Threads manually, in this case I have to revert back to CountDownLatch to be able to wait for the threads to finish:

Version without ExecutorService

public static void main(String[] args) {
  int count = 50;

  CountDownLatch latch = new CountDownLatch(count);
  CyclicBarrier barrier = new CyclicBarrier(count);

  Random random = new Random();
  for (int i = 0; i &lt; count; i++) {
    new Thread(() -&gt; {
      try {
        System.out.println("Thread starts");
        // startup
        Thread.sleep(random.nextInt(10));
        // wait for other threads
        System.out.println("Thread waits");
        barrier.await();
        // process whaterver should be processed
        System.out.println("Thread works");
        Thread.sleep(random.nextInt(1000));
        System.out.println("Thread finished");
      } catch (Exception e) {
        System.err.println("Worker thread inrerrupted");
      } finally {
        latch.countDown();
      }
    }).start();
  }

  try {
    // wait for the threads to be done
    latch.await();
    System.out.println("== End == ");
  } catch (InterruptedException e) {
    System.err.println("Starting inrerrupted");
  }
}  


Even in this version it remains pretty short and simple thanks to lambda in Java 8.