I have had this issue before and this is really frustrating.
I am having this problem only on the Mac. I hate the latest version according to my Creative Cloud Application. But it looks like I have two different version.
Can someone help please.
Looks like when I updated my After Effects, My older version of After Effects were still there. And my shortcut was not updated. That is why I was facing this issue.
You need to have the new version of After Effects installed.
AE CC 2015.3 (version number 13.8.1.x) is a new version and it works with the new version of Media Encoder.