The keyboard shortcut cmd / ⌘ + shift + N no longer works on my MacBook Pro (mid-2009 15", FWIW). I've tested this in several apps, such as Sublime Text and TextWrangler, most of which use this key combination to open a new window. Similar shortcuts like ⌘ + shift + Z work as expected. As far as I know, I haven't made any recent changes that would have caused this. One day it worked, the next it didn't.
If that doesn't reveal the culprit, you might want to look to see if you have any "Input Manager hacks" installed. These are third-party tools that use a skanky method to modify the behavior of the system and other apps. Some of the best known Input Manager hacks include SIMBL (and tools that use SIMBL, such as Afloat) and APE (Unsanity's Application Enhancer, and related "Haxies"). If you find any input manager hacks, remove them according to their instructions.