Symptoms

Tests error out on your test runner, claiming:

'Could not start a new session.
Possible causes are invalid address of the remote server or browser
start-up failure.'

On the Sauce Labs side, jobs are stopped with an error:

"Test did not see a new command for 90 seconds. Timing out."

Cause

Your language's HTTP library assumes all requests succeed in 60 seconds or less, and anything longer is a bad server.  Appium is taking more then 60 seconds to start, so your language's HTTP library throws an error.  We don't notice your test is abandoned until it starts, so we wait for 90 seconds for you to send commands and then we give up.

Why does it take more then 60 seconds to bring up a session?  Primarily, because the device simulators/emulators, as well as their testing frameworks, are slow to start.  Exacerbating the problem, they often crash on launch and Appium has to retry starting them.

Example

Here's an example timeline showing what happens.  Times here are not precise, but intended to show roughly when things happen.  This example is for the iOS simulator but this also happens for Android sessions

0:00 - Your test code requests a new session from Sauce Labs
0:01 - Sauce Labs receives the request, finds a VM and boots it up 
0:02 - Appium starts running and tries to bring up the iOS simulator
0:20 - Apple Instruments starts
0:21 - Apple Instruments dies
0:26 - Apple Instruments starts
0:30 - iOS Simulator starts
0:45 - iOS Simulator crashes before fully started
0:50 - Appium notices iOS Simulator crashed and restarts it
1:00 - Your test code's http library decides that Sauce Labs doesn't exist or is broken, and closes the connection
1:20 - iOS Simulator is fully launched
1:20 - Appium begins to wait for Selenium commands.  No commands happen because your tests have given up
2:50 - 90 seconds have passed since Appium was fully ready.  Sauce Labs assumes something is wrong and shuts down the test

Solution

Extend the HTTP timeout for your language.  This is not the timeout delay of Appium or Selenium or even your test framework, but the underlying language you're using such as Java or Ruby.