[SalesForce] Install Script Batch Job failing (sObject type ‘Contact’ is not supported)

This is my scenario:
I have a managed package, with quite some logic in it, and 2 triggers on normal SObjects, Lead and Contact the 2 triggers populate a field (included in the managed package) on the corresponding SObjects in the beforeUpdate and beforeInsert. (those fields are necessary for my package to properly work)

I wrote 2 simple batch jobs (see below) with the goal of populating those fields when the package gets installed on an org (in case the org has Leads and Contacts already, and those fields weren't populated). And an install Script (see below), which just starts both of the batch jobs, I then added the Install Script in the "Install Script" field on the managed package.

When the package installs, the code gets executed properly, the batches start, but when I look at the Apex Jobs the 2 batches failed with the error messages:

Batch Apex Failed First error: sObject type 'Lead' is not supported.

Batch Apex Failed First error: sObject type 'Contact' is not
supported.

Here is the Batch (as you can see the only thing this batch does, is making sure the contacts go through my trigger)

public with sharing class ContactPopulatePackageFieldBatch implements Database.Batchable<sObject>
{
    public Database.QueryLocator start(Database.BatchableContext BC)
    {
        String query = 'SELECT Id, PackageField__c FROM Contact WHERE PackageField__c = NULL OR PackageField__c = \'\'';
        return Database.getQueryLocator(query);  
    }

    public void execute(Database.BatchableContext BC, List<Contact> scope)
    {
        Database.update(scope,false);
    }

    public void finish(Database.BatchableContext BC)
    {  
        // Nothing to see here
    }
} 

Then I created an InstallScript to trigger those batch jobs on install of my package:

public with sharing class InstallLogic implements InstallHandler
{
    public void onInstall(InstallContext context)
    {
        // start a lead batch
        LeadPopulatePackageFieldBatch leadBatch = new LeadPopulatePackageFieldBatch();
        Database.executeBatch(leadBatch,1000);

        // start a contact batch
        ContactPopulatePackageFieldBatch contactBatch = new ContactPopulatePackageFieldBatch();
        Database.executeBatch(contactBatch,1000);
    }
}