I just set up a new Emacs 25 installation on a new computer.
After installing the smex package, the smex command wouldn’t work, stating “no such file or directory: ido-completing-read+”. After installing the ido-completing-read+ package, it started working.
I believe smex should declare a dependency so that ido-completing-read+ will be installed automatically.