Can you set them individually under Edit > Keyboard Shortcuts?
Was there any non-manual set up solution? I installed CS6 recently, and all PS commands are the same invalid characters you describe.
I am still yet to find a solution to this problem. I can update the entries manually but after restarting PS, they reset.
I am sorry to hear that... for both of us.
I put it out there again (using part of your well articulated email) and hopefully that can generate a resolution.