I had the same situation but I already solved twice. The first time is after nuking my machine and the second time is compiling distribution package on other machine.
1. See Key Chain and see if you can find your "private key" when you generate certification on your local machine. Usually your name is on it.
2. If you do not have the original private key, I guess, you have to request / generate and recreate certificate on their website. If you already have one in other machine or backup, Right click on the private key -> Export -> and move then double click at the target machine.
3. If you have a correct provisioning file, you will see it in drop down. If you see some funky code, just restart xcode and see if you can see the provision file.
You can verify validity of your app by typing command in terminal
codesign -vvvv MyApp.app
It should say, your binary is valid.
BTW, does anyone has problem to "update" the same application? I used exact same configuration, but upload never succeeded. See this thread if you have the same problem.
http://discussions.apple.com/thread.jspa?threadID=1590980&tstart=0