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.

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

example code https://code.google.com/p/where-is-my-car/source/browse/src/com/prashanth/whereismycar/LocaterMapActivity.java