Android application becomes slow after multiple callbacks - what's wrong here?

I have an application that parses through a user's facebook messages, and due to an extremely annoying limitation by the facebook API that only lets you receive 25 messages per API call, I have to use some weird quasi-recursive method to parse through the messages so I can handle pagination. My issue arose when I attempted to make my application sleep in the scenario where we exceeded requests before trying again.

I noticed that the app would shoot out really fast, parsing through several api calls per second. But as the app dragged on and the requests hit several hundreds, it slowed to a crawl of like maybe 1 per 5 seconds. Does anybody see what is slowing me down here?

Relevant portions of my code:

I start the parsing from a service, which basically makes the initial request for 25 messages (and the links to every one after that) and calls retrieveMsgs().

@Override
public int onStartCommand(Intent intent, int flags, int startID){

    if(intent!=null) {
        id = intent.getStringExtra("id");
    }

    Session session = Session.getActiveSession();
    new Request(session, id + "/comments", null, HttpMethod.GET, new Request.Callback() {
        @Override
        public void onCompleted(Response response) {
        try {
            JSONArray msgs = response.getGraphObject().getInnerJSONObject().getJSONArray("data");
            populateData(msgs);

        } catch (JSONException e) {
            e.printStackTrace();
        }
        Request next = response.getRequestForPagedResults(Response.PagingDirection.NEXT);
        retrieveMsgs(next);
        }
    }).executeAsync();
    return START_STICKY;
}

and this calls retrieveMsgs, which will call itself until it finishes parsing each 25 message array from the Facebook API. It basically parses the 25 messages and then checks to see if it received a link to the next page, and quits if it doesn't.

public void retrieveMsgs(final Request next) {
    Log.i("api calls", apiCalls+"");

    if (next != null) {
        next.setCallback(new Request.Callback() {
            public void onCompleted(Response response) {
                try {
                    if (response.getGraphObject() == null) {
                        // we exceeded our limit, sleep for a bit before trying again
                        try {
                            Thread.sleep(240000);
                        }
                        catch(Exception e){

                        }
                        retrieveMsgs(next);      // restart the method call
                        Log.i("hello", "is this slowing us down?");
                        return;
                    }

                    JSONArray msgs = response.getGraphObject().getInnerJSONObject().getJSONArray("data");
                    populateData(msgs);

                    Request next2 = response.getRequestForPagedResults(Response.PagingDirection.NEXT);

                    if (next2 != null) {
                        apiCalls++;
                        retrieveMsgs(next2);
                    } else {
                        showDoneNotif();
                    }} catch (JSONException e) {
                    e.printStackTrace();
                }
            }
        });
        next.executeAsync();

    }

}

I have difficulty tracking code through inner classes and callbacks and whatnot, so I'd really appreciate it if anybody could explain what is potentially going wrong here. The slowdown really kills the viability of the app after 20,000 messages or so, and with potentially hundreds of thousands of messages per conversation, I can't reasonably move on from this.