This is kinda a repost and I'm sorry for that, but the last time I posted it I thought I got it down but apparently not. When I tried to call the Service I use to get this error Caused by: java.lang.IllegalStateException: GoogleApiClient is not connected yet.
Because I was trying to call LocationServices before GoogleApiClient was even connected. So after changing the code up a bit I wasn't getting the error anymore, in fact I wasn't getting anything in logcat anymore. 
This is how I start my Service from SearchActivity.class:
SearchActivity.class
 button = (Button)findViewById(R.id.buttonPressed);
    button.setOnClickListener(new View.OnClickListener() {
        @Override
        public void onClick(View v) {
            startService(new Intent(getBaseContext(), LocationService.class));
        }
    });
This is the Service:
LocationService.class
public class LocationService extends Service implements GoogleApiClient.ConnectionCallbacks,
        GoogleApiClient.OnConnectionFailedListener, LocationListener {
    // LogCat tag
    private static final String TAG = LocationService.class.getSimpleName();
    private final static int PLAY_SERVICES_RESOLUTION_REQUEST = 1000;
    private Location mLastLocation;
    // Google client to interact with Google API
    private GoogleApiClient mGoogleApiClient;
    // boolean flag to toggle periodic location updates
    private boolean mRequestingLocationUpdates = false;
    private LocationRequest mLocationRequest;
    // Location updates intervals in sec
    private static int UPDATE_INTERVAL = 10000; // 10 sec
    private static int FATEST_INTERVAL = 5000; // 5 sec
    private static int DISPLACEMENT = 10; // 10 meters
    @Override
    public void onCreate() {
        super.onCreate();
        mGoogleApiClient = new GoogleApiClient.Builder(this)
                .addConnectionCallbacks(this)
                .addOnConnectionFailedListener(this)
                .addApi(LocationServices.API).build();
    }
    @Override
    public int onStartCommand(Intent intent, int flags, int startId) {
        if (mGoogleApiClient != null) {
            if(mGoogleApiClient.isConnected()) {
                if (mLocationRequest != null) {
                    togglePeriodicLocationUpdates();
                }
            }
        }
        return START_NOT_STICKY;
    }
    @Override
    public IBinder onBind(Intent intent) {
        return null;
    }
    protected void createLocationRequest() {
        mLocationRequest = new LocationRequest();
        mLocationRequest.setInterval(UPDATE_INTERVAL);
        mLocationRequest.setFastestInterval(FATEST_INTERVAL);
        mLocationRequest.setPriority(LocationRequest.PRIORITY_HIGH_ACCURACY);
        mLocationRequest.setSmallestDisplacement(DISPLACEMENT);
    }
    private void togglePeriodicLocationUpdates() {
        mGoogleApiClient.connect();
        if(mGoogleApiClient.isConnected()) {
            if (!mRequestingLocationUpdates) {
                mRequestingLocationUpdates = true;
                startLocationUpdates();
                Log.d(TAG, "Periodic location updates started!");
            } else {
                mRequestingLocationUpdates = false;
                // Stopping the location updates
                stopLocationUpdates();
                Log.d(TAG, "Periodic location updates stopped!");
            }
        }
    }
    protected void stopLocationUpdates() {
        LocationServices.FusedLocationApi.removeLocationUpdates(
                mGoogleApiClient, this);
    }
    protected void startLocationUpdates() {
        mGoogleApiClient.connect();
        if(mGoogleApiClient.isConnected()) {
            LocationServices.FusedLocationApi.requestLocationUpdates(
                    mGoogleApiClient, mLocationRequest, this);
        }
    }
    @Override
    public void onConnected(Bundle arg0) {
        createLocationRequest();
    }
    @Override
    public void onConnectionSuspended(int arg0) {
        mGoogleApiClient.connect();
    }
    @Override
    public void onConnectionFailed(ConnectionResult result) {
        Log.i(TAG, "Connection failed: ConnectionResult.getErrorCode() = "
                + result.getErrorCode());
    }
@Override
public void onLocationChanged(Location location) {
    // Assign the new location
    mLastLocation = location;
    Toast.makeText(getApplicationContext(), "Location changed!",
            Toast.LENGTH_SHORT).show();
}
@Override
public boolean stopService(Intent name) {
    return super.stopService(name);
}
AndroidManifest.xml
    </activity>
    <service android:name=".LocationService">
    </service>
Edit:
Well I figured how to get it working. But now I'm facing the problem of having to click the button 2 times before it would start normally. Only had to change the onStartCommand() a bit.
 @Override
    public int onStartCommand(Intent intent, int flags, int startId) {
        if (mGoogleApiClient != null) {
            mGoogleApiClient.connect();
            if(mGoogleApiClient.isConnected()) {
                if (mLocationRequest != null) {
                    togglePeriodicLocationUpdates();
                }
            }
        }
        return START_NOT_STICKY;
    }
				
                        
You should read the documentation on GoogleApiClient, particularly (for the question at hand) the connect() method. I've highlighted the relevant portion:
So, this is what currently happens with your code:
What you should do is implement onConnected(). From there, call togglePeriodicLocationUpdates() instead of doing that in onStartCommand(). This will accomplish what you want: