Keyboard shortcut stopped working in Safari 6.0
Go to System Preferences.
Click on “Keyboard.” Navigate to Keyboard Shortcuts.
Select Application Shortcuts in the left pane and remove existing shortcuts for Safari, if any.
Add a shortcut by clicking the “+” button. In the Menu Title field, type “Enter Full Screen.” Remember, you have to type the exact title as it appears in Safari.
Add another shortcut and in the menu title field and type “Exit Full Screen” in the Menu Title field.
Make sure there are no conflicts with the shortcut combination that you choose to use.


Hope this helps.

PS: Be careful of the space between “Full” and “Screen” in the menu title.