Market reporting my manifest doesn't have a permission listed, when it definitely does?

I've implemented C2DM, I'm getting this exception for a small fraction of users (as reported by marketplace crash reporting):

java.lang.RuntimeException: Unable to start activity
  ComponentInfo{com.me.app/com.me.app.MyActivity}: 
  java.lang.SecurityException: 
    Not allowed to start service Intent {
      act=com.google.android.c2dm.intent.REGISTER 
      pkg=com.google.android.gsf (has extras) 
    }
  without permis开发者_如何学JAVAsion com.google.android.c2dm.permission.RECEIVE
  ...
Caused by: java.lang.SecurityException: 
  Not allowed to start service Intent {
    act=com.google.android.c2dm.intent.REGISTER 
    pkg=com.google.android.gsf (has extras) } without permission
     com.google.android.c2dm.permission.RECEIVE
    at android.app.ContextImpl.startService(ContextImpl.java:864)
  ...

I definitely have the "com.google.android.c2dm.permission.RECEIVE" permission in my manifest, it's working fine for thousands of users. Not sure why I'm being told these users don't have the permission requested?

Thanks