After a form submit, can I create multiple batches based on the maximum table size for the serialized batch string and how can this be done?

I am using a batch process to pass users to an external site using their API.

For each user I set $batch['operations'][] = array('process_funcion', array(LIST OF VARIABLES));

The batch processing works for upto 5000 users; anything over that I get the following error:

Access denied
You are not authorized to access this page.

I thought this had to do with max_packet size, but I am not to sure of that anymore.

The batch is being initiated after a form is being processed.

Do you have any ideas on how I can process 5000 users at a time, or why I am getting this error?

I think that the insert to the batch table is to big, so I am trying to split this into separate batches like this.

$contactCount = 1;
foreach ($contacts as $contact) {
  $batch['operations'][] = array('_contact_add_batch', array($module, $acc_id, $Group_ID, $verb,$contact));
  //Due to max_packet_size restrictions, need to set multiple batches
  if (($contactCount % 2000) == 0){
    batch_set($batch);
  }
  $contactCount++;
}
// For the last set of batches, in the event that there is not 2000, lets add them also.
if (!empty($batch['operations'])) {
  batch_set($batch);
}

I am still getting the Access Denied error.