While I believe most already tried this, my screen had some parts cropped out, and this was solved by changing the tv's widescreen setup (changing my PS3 setup or my game's setup didn't work). My tv has two types of widescreen configurations and other 2 non-widescreen ones, I kept changing it until I got the whole screen perfectly fit and I had no cropped edges. I didn't change the resolution on my TV either.

I am not at home right now to write the setup that worked for me, but if anyone that is having this problem hadn't tried that before it is worth it.