Application Shortcuts not working?

I may well be wrong, but I don't think there is a native way to launch applications with keyboard shortcuts. The application shortcuts bit in System Preferences > Keyboard is to do with shortcuts that you can use when you're already in the given app.

If you want to setup keyboard shortcuts to launch apps though, you can download (and buy) Apptivate from the app store, or if you'd prefer a free option, you can try the following (from Mac OS X Hints):

To do so, create a Service using Automator with a single action to launch an application. Set the conditions of this service to receive "no input," and make it available in all applications. Save the Service and create a shortcut to it on the Keyboard Shortcuts tab of the Keyboard System Preferences panel.

Note that the shortcut will not work in apps (Firefox, for one) that don't support Services.