Not only do you have to add your own certificate (iPhone Developer: Johny Appleseed) you must also add Apple's Certificate Assigning Authority to your local keychain as well.
EDIT:
The certificate section in the program portal has the following info:
Downloading and Installing Development
Certificates In the ‘Certificates’ >
’Distribution’ section of the Portal,
control-click the WWDR Intermediate
Certificate link and select “Saved
Linked File to Downloads” to initiate
download of the certificate. On your
local machine, double-click the WWDR
Intermediate certificate to launch
Keychain Access and install. Upon CSR
approval, Team Members and Team Admins
can download their certificates via
the ‘Certificates’ section of the
Program Portal. Click ‘Download’ next
to the certificate name to download
your iPhone Development Certificate to
your local machine. On your local
machine, double-click the downloaded
.cer file to launch Keychain Access
and install your certificate. Team
Members can only download their own
iPhone Development Certificates. Team
Admins have the authority to download
the public certificates of all of
their Team Members. Apple never
receives the private key for a CSR.
The private keys are not available to
anyone except the original key pair
creator and are stored in the system
keychain of that Team Member.
The certificate assigning authority should be something like applewwdrca.cer, there are screen shots and more info in the "How To" section.
EDIT 2:
Read through this Provisioning HowTo carefully (as well as the other HowTo tabs in the program portal), provisioning is a pain in the ass tedious process, if this documentation does not fix your problem then you need to burn one of your free support cards and call Apple because there is a problem with your particular machine. You should have gotten 2 of those support requests when you entered the program, if you used them all you can buy more.