I was finally able to fix it.
The problem is with the App Store version.
If you installed Evernote from the App Store, simply delete it from your Applications folder and download the current version from the Evernote website. Install it and it will work.
Even though both versions are supposed to be identical, I have a feeling the App Store version is sandboxed by the system and causes the problem with Preview. Hopefully they can fix that in the future but for now this simple fix works without having to go back to a legacy version.