Some details about your footage and sequence would be helpful.
Chances are pretty good that you've got video that doesn't match your sequence... i.e., you're putting HD video in an SD sequence. To get the video into the proper type of sequence, drag your video file to the New Item icon in your bin and PPro will automatically create the best sequence to match your video. If you're still having trouble, check to see if your program monitor is set at anything other than "fit." It could be that it's set at a higher resolution than you have room for.
>add a video
Read Bill Hunt on a file type as WRAPPER http://forums.adobe.com/thread/440037?tstart=0
What is a CODEC... a Primer http://forums.adobe.com/thread/546811?tstart=0
What CODEC is INSIDE that file? http://forums.adobe.com/thread/440037?tstart=0
Report back with the codec details of your file, use the programs below
For PC http://www.headbands.com/gspot/ or http://mediainfo.sourceforge.net/en
For Mac http://mediainfo.massanti.com/
Once you know exactly what it is you are editing, report back with that information... and your project setting, and if there is a red line above the video in the timeline, which indicates a mismatch between video and project
I think that others have nailed the issue, but wanted to point out that the Title Safe and Action Safe Guides are just that - Guides, and are for your information only.