Did you also regenerate your provisioning profile? This sounds like the provisioning profile doesn't contain the certificate you've uploaded.
I had regenerated the profile, but it looks like perhaps the profile was attached to an old cert. I added both available certs I had (both show up with the same name in the Apple dev portal, unfortunately) and it worked.
Thanks for the pointer.