Okay, I think I solved it but I'm not sure how.
While I
had set the particular editing applications for NEF, JPG and PSD, I
hadn't set the more general 'Default application to edit photos' setting just above; it was still on 'Let the Finder open files'.
I set that to PS CS4 and tried again and now E to edit opened in the correct application no matter if NEF or JPG.
The weird bit is, I tried switching that setting back to 'Let the Finder open files' expecting it E to stop working, but it didn't; it still works in Preview and Contact Sheet.
I definitely wasn't hitting the wrong key, I promise!
Kirk, just noticed your reply. Yep, I tried editing from the right-click and that worked.