If you used the Youtube widescreen HD preset, and the result is
an intact .mp4 file you should be no trouble uploading it to YouTube.
I just tested exporting with the YouTube Widescreen HD encoding preset from Premiere Pro CS5 and uploading the result to Youtube. It worked fine.
Give us more details about exactly what you're doing and exactly what's going wrong---ideally, a screenshot of your export settings and a screenshot of what Youtube is telling you.
Also, it's good practice to give the exact version number of Premiere Pro that you're using, you're operating system, and details of your footage and sequence settings.