The code signing step is notoriously fussy and buggy. Make sure you have followed the steps to get the certificate and profile from Apple absolutely exactly. Then check your build settings under 'code signing identity'.
You don't need a device connected though it is handy for checking it all worked. However I have found on occasion I've needed to edit the project file by hand - you shouldn't need to do that, especially with 3.xSDK as it is a bit better at the code signing stuff.
Possible reasons for the error are
1) a mismatch in the name that is in the certificate, vs the name that is set in your project. However 3.0 is supposed to automatically match 'iPhone distribution' and not be so fussy about an exact match.
2) You haven't added the certificate you got from apple to the keychain
3) Your project file has got confused and has wrong profile settings due to a bug in XCode. Shouldn't really happen but I find myself going into the project package contents and editing the project file in textedit sometimes - not for the faint of heart, and you should make a backup if you try this.
4) Make sure the profile you got from apple is installed properly in xcode (look in the organiser window).
5) To check that it works OK it does help to try installing it on a device, though it's not strictly necessary. Using the application uploader rather than the itunesconnect website to upload the distribution file is another good check, it should object if the file is not signed properly. (Though having said that I've had trouble with the app uploader and had to use the website upload sometimes).
The short version is there is a pretty good chance you've done everything right and just hit a bug in xcode. Even when it seems to have worked, it often hasn't. The whole thing is a mess. Just try redoing the steps and changing the code signing identity in xcode. Also clean out any old profiles you're not using, to give xcode less chance of picking the wrong one.