Game Uploads to Google Store, but Gives Signing Error to Users?

We've run into an odd problem recently, trying to put a game on the Google market. We build the game (signed), and it uploads correctly to the market with no issues. When a user tries to install it though, they get an error about the application not being signed properly. Has anyone experienced this issue and/or knows what's causing it? We've tried:

• Switching to Java 1.6, 32-bit.

• Uploading it as a new game to the store, with a different name.

• Using a new keystore.

Which all result in the same issue - uploads fine, won't install for users.

AndroidManifest.xml: http://schemas.android.com/apk/res/android" package="com.unity3d.player" android:installLocation="preferExternal" android:versionCode="1" android:versionName="1.0">

         <application android:name="com.prime31.EtceteraApplication"
             android:icon="@drawable/app_icon"
             android:label="@string/app_name"
             android:debuggable="true">
             <activity android:name="com.unity3d.player.UnityPlayerProxyActivity"
                       android:label="@string/app_name"
                       android:configChanges="fontScale|keyboard|keyboardHidden|locale|mnc|mcc|navigation|orientation|screenLayout|screenSize|smallestScreenSize|uiMode|touchscreen">
                 <intent-filter>
                     <action android:name="android.intent.action.MAIN" />
                     <category android:name="android.intent.category.LAUNCHER" />
                 </intent-filter>
             </activity>
             <activity android:name="com.unity3d.player.UnityPlayerActivity"
                       android:label="@string/app_name"
                       android:configChanges="fontScale|keyboard|keyboardHidden|locale|mnc|mcc|navigation|orientation|screenLayout|screenSize|smallestScreenSize|uiMode|touchscreen">
             </activity>
             <activity android:name="com.unity3d.player.UnityPlayerNativeActivity"
                       android:label="@string/app_name"
                       android:configChanges="fontScale|keyboard|keyboardHidden|locale|mnc|mcc|navigation|orientation|screenLayout|screenSize|smallestScreenSize|uiMode|touchscreen">
                 <meta-data android:name="android.app.lib_name" android:value="unity" />
                 <meta-data android:name="unityplayer.ForwardNativeEventsToDalvik" android:value="true" />
             </activity>
             <activity android:name="com.unity3d.player.VideoPlayer"
                       android:label="@string/app_name"
                       android:configChanges="fontScale|keyboard|keyboardHidden|locale|mnc|mcc|navigation|orientation|screenLayout|screenSize|smallestScreenSize|uiMode|touchscreen">
             </activity>
            
             <!-- ACTIVITIES -->
             <activity android:name="com.prime31.EtceteraProxyActivity"></activity>
             <activity android:name="com.prime31.WebViewActivity" android:configChanges="orientation"></activity>
             <activity android:name="com.prime31.P31VideoPlayerActivity" android:configChanges="keyboard|keyboardHidden|orientation"></activity>
             <receiver android:name="com.urbanairship.CoreReceiver">
             <intent-filter>
             <action android:name="android.intent.action.BOOT_COMPLETED" />
             <action android:name="android.intent.action.ACTION_SHUTDOWN" />
             </intent-filter>
             </receiver>
            
             <receiver android:name="com.urbanairship.push.c2dm.C2DMPushReceiver" android:permission="com.google.android.c2dm.permission.SEND">
             <intent-filter>
             <action android:name="com.google.android.c2dm.intent.RECEIVE" />
             <category android:name="com.prime31.Etcetera" />
             </intent-filter>
             <intent-filter>
             <action android:name="com.google.android.c2dm.intent.REGISTRATION" />
             <category android:name="com.prime31.Etcetera" />
             </intent-filter>
             </receiver>
             <service android:name="com.urbanairship.push.PushService" android:process=":com.urbanairship.push.process"/>
      
             <!-- META-DATA -->
      
         </application>
        
         <!-- PERMISSIONS -->
             <uses-permission android:name="android.permission.INTERNET"/>
             <uses-permission android:name="android.permission.ACCESS_NETWORK_STATE"/>
             <uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED"/>
             <uses-permission android:name="android.permission.READ_PHONE_STATE"/>
             <uses-permission android:name="android.permission.VIBRATE"/>
             <uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE" />
            
             <permission android:name="com.prime31.Etcetera.permission.C2D_MESSAGE" android:protectionLevel="signature" />
             <uses-permission android:name="com.prime31.Etcetera.permission.C2D_MESSAGE" />
             <uses-permission android:name="com.google.android.c2dm.permission.RECEIVE" />
        
     </manifest>