And if that doesn't work, you need to also ensure:
1. Your HDMI cables are High Speed certified (if you're not sure, let us know what make they are).
2. If running through an AV amp, the PS3 must be running through compliant HDMI 1.4 ports (again, if this is the case and you're not sure, let us know the make and model).