java.lang.IllegalStateException: Not connected. Call connect() and wait for onConnected() to be called.

This happens when you request for locationupdates before the actual location connection is established. Instead use a boolean variable to check if connection is established or call for locationupdates as below in onConnected.

        public void onConnected(Bundle connectionHint) {
                Toast.makeText(this, "Connected", Toast.LENGTH_SHORT).show();
                mLocationClient.requestLocationUpdates(mLocationRequest, this);

example code