A little update from R*:
1. Delete L.A. Noire Game Data (not save data) from the PS3 Game Data Utility. On Xbox 360, clear the cache (My Xbox, System Settings, Device Options, Clear System Cache).
2. Create a temporary PS3 profile to ensure new save files are created. On Xbox 360, create a Silver Xbox Live Gamertag.
3. Launch L.A. Noire and try again. Try playing while signed out of PSN.
4. Check L.A. Noire disc for scratches, dust, dirt or other damage. Clean if necessary.
5. Check other game-discs on your PS3 or Xbox 360 to test whether it's L.A. Noire or the console playing up.
6. Try your L.A. Noire disc in a different console
http://www.psu.com/[UPDATE]-Users-report-issues-running-LA-Noire-on-old-PS3-models--a011702-p0.php
Oops... Or maybe I should not be posting it here since it's a negative PS3 thread? Oh, guess what? It helps Xbox 360 users as well. So it's now alright, right...?