Google Cloud Messaging breaks project

Question

In a strange turn of events, adding GCM to my android project is somehow breaking it.

Trying to debug the project in either an emulator or on a device results in a "Failure [install_parse_failed_no_certificates]." Which makes no sense as A) debugging the application worked perfectly fine prior to adding GCM and works when I remove GCM and B) debugging from Android Studio automatically signs the resultant apk.

I then created a new project and added GCM to it, and it ran just fine. Adding all of the original files to this new project however breaks it, causing the same messages as above.

To be clear, it builds perfectly fine, it (supposedly) signs when I attempt to manually sign it perfectly fine, but installing it is failing from both Android Studio and manual attempts to install.

Any help or insights on what the issue(s) could be would be most appreciated.

Edited to include the build config files.

AndroidManifest.xml

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.company.app" >
    <uses-permission android:name="android.permission.INTERNET" />
    <uses-permission android:name="android.permission.BLUETOOTH" />
    <uses-permission android:name="android.permission.BLUETOOTH_ADMIN" />

    <!-- [START gcm_permission] -->
    <uses-permission android:name="com.google.android.c2dm.permission.RECEIVE" />
    <uses-permission android:name="android.permission.WAKE_LOCK" />
    <!-- [END gcm_permission] -->

    <uses-feature
        android:name="android.hardware.bluetooth_le"
        android:required="true" />

    <application
        android:allowBackup="true"
        android:icon="@mipmap/ic_launcher"
        android:label="@string/app_name"
        android:supportsRtl="true"
        android:theme="@style/AppTheme" >
        <activity android:name=".MainActivity" >
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />

                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
        <!-- [START gcm_receiver] -->
        <receiver
            android:name="com.google.android.gms.gcm.GcmReceiver"
            android:exported="true"
            android:permission="com.google.android.c2dm.permission.SEND" >
            <intent-filter>
                <action android:name="com.google.android.c2dm.intent.RECEIVE" />
                <category android:name="com.company.app" />
            </intent-filter>
        </receiver>
        <!-- [END gcm_receiver] -->

        <!-- [START gcm_listener] -->
        <service
            android:name="com.company.app.AppGcmListenerService"
            android:exported="false" >
            <intent-filter>
                <action android:name="com.google.android.c2dm.intent.RECEIVE" />
            </intent-filter>
        </service>
        <!-- [END gcm_listener] -->
        <!-- [START instanceId_listener] -->
        <service
            android:name="com.company.app.AppInstanceIDListenerService"
            android:exported="false">
            <intent-filter>
                <action android:name="com.google.android.gms.iid.InstanceID"/>
            </intent-filter>
        </service>
        <!-- [END instanceId_listener] -->
        <service
            android:name="com.company.app.RegistrationIntentService"
            android:exported="false">
        </service>

        <activity
            android:name="com.company.app.RegisterActivity"
            android:label="@string/title_activity_register"
            android:windowSoftInputMode="adjustPan" >
        </activity>
        < !-- More activities -- >
    </application>
</manifest>

app gradle:

apply plugin: 'com.android.application'
apply plugin: 'com.google.gms.google-services'

android {
    compileSdkVersion 23
    buildToolsVersion "23.0.1"

    defaultConfig {
        applicationId "com.company.app"
        minSdkVersion 21
        targetSdkVersion 23
        versionCode 1
        versionName "1.0"
    }
    buildTypes {
        release {
            minifyEnabled false
            proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.pro'
        }
    }
}

dependencies {
    compile fileTree(dir: 'libs', include: ['*.jar'])
    compile files('libs/bcpkix-jdk15on-152.jar')
    compile files('libs/gson-2.3.1.jar')
    compile files('libs/bcprov-jdk15on-152.jar')
    compile project(':volley-release')
    compile 'com.google.android.gms:play-services-gcm:8.1.0'
    compile 'com.android.support:support-v4:23.0.1'
    compile 'com.android.support:appcompat-v7:23.0.1'
    compile 'org.whispersystems:curve25519-android:0.2.4'
    compile 'com.squareup.okhttp:okhttp:2.4.0'
    compile 'com.squareup.okhttp:okhttp-urlconnection:2.4.0'
    compile 'com.squareup.okio:okio:1.5.0'
}

top-level gradle:

// Top-level build file where you can add configuration options common to all sub-projects/modules.

buildscript {
    repositories {
        jcenter()
    }
    dependencies {
        classpath 'com.android.tools.build:gradle:1.3.0'
        classpath 'com.google.gms:google-services:1.4.0-beta3'
        // NOTE: Do not place your application dependencies here; they belong
        // in the individual module build.gradle files
    }
}

allprojects {
    repositories {
        jcenter()
    }
}

task clean(type: Delete) {
    delete rootProject.buildDir
}