How to create a 'New Email with Attachment' option in Finder?
Is the service present and enabled in the Services section of Keyboard Preferences?

You should see this:


If it's not there for some reason, you can recreate it easily in Automator. 

Create a new Service in Automator, add the "New Mail Message" action to the workflow, and change the first drop down at the top so it reads "Service receives selected files and folders in any application". It should look like this:



Then save it, and you should have it available in your services menu.