Todd Kopriva, from Adobe, has just done a nice TUTORIAL, addressing "black bars," around the image in the Program Monitor. Todd uses PrPro CS 5.5 for his demo, but nearly everything, save a few mechanical differences, will apply to other versions of PrPro, and also PrE. The concept is exactly the same, really for almost any NLE (Non Linear Editor) program. If you get into the mechanics, and realize that you cannot find something that Todd mentions, it's either not in your version of Premiere (like Sequences in PrE - there, think about Project Presets instead), or is located elsewhere, and you need to consult your program's Help File.
For a little more info on PAR (Pixel Aspect Ratio), that Todd touches on, see this ARTICLE.
Remember, some of the mechanics might be different in your version of Premiere, but the concept is exactly the same.
Hope that this explains those black bars, where they came from and how to address them.