My guess that some something is grabbing Command-A. The problem is finding out what.
When you open the Edit menu, do you still see “Select All ⌘A” as a menu item?
Look through the shortcuts in the shortcuts tab of the keyboard pane in System Preferences. If there is something defined for Command-A there, it will take precedence.
Logout and then login again, but holding down Shift right after (or while) pressing Return. This will prevent the auto-launching of your Login Items (see the Login Items tab in the Accounts pane of System Preferences). Now check to see if Command-A works. If it does, the problem is probably one of your Login Items. You can try launching them one-by-one by double clicking them in the Login Items tab. Check your Command-A functionality after each one. When it stops working the most recently launched app is to blame. Go check its configuration. It is probably something innocent like a launcher or shortcut app that has been configured incorrectly.
It could also be the keyboard itself. Have you tried another keyboard or the other Command key? You might try launching the Keyboard Viewer to check if it is reporting the key presses. In System Preferences, goto the Universal Access pane, pick the Input Menu tab, check Keyboard Viewer, check Show input menu in menu bar, then pick Show Keyboard Viewer from the new menu item (it may look like a flag) in the menu bar. To get rid of the new menu item, Command-drag it off the menu bar or uncheck the ‘show in menu bar’ option.
