Welcome to the forums.
Your sequence settings do not match your clip settings.
Create a new sequence and choose a DV NTSC preset and put one of your clips in the new sequence. Does the clip fill the program monitor?
If so you can copy the clips from the old sequence and paste them into the new one.
If not then your clips are not 720x480. You can use a utility to determine the codecs used in your source files.
You will also find links to many free tutorials in the PremiereProPedia that will quickly show you how things are done in Premiere Pro.
Thank you Eddie. You were right-on! I'm always scared of the simple stuff, it seems the easiest to screw-up!
It used to be a bit more simple pre-CS4, as one had to do the settings only in the Project, when started. Now, with CS4, one can have different settings per Sequence too. Just one more place to check.