I had the same issue and traced the problem to the browser.
At first I applied for the free cert using Chrome and collected it (after receiving the email from Comodo) using Chrome. This placed a user.crt file in my Downloads folder (the default for Chrome, I presume). All seemed fine as I’ve double-clicked on the user.crt file, selected “Install…”, and completed with “Finish”.
Checking the certificate store (using “crtmgr.msc” at the “Run…” prompt) also made it appear that I had done everything correctly. After a lot more Googling, hacking, and rebooting, I’ll decided to start over. This time using Internet Explorer 11 as the browser. I had to revoke my previous certificate before proceeding.
After that everything went fine and Outlook 2016 recognized the cert immediately (File->Options->Trust Center->Email Security->Choose…).
Other notes: Don’t waste your time with Firefox or Edge. Go straight to IE 11.
My configuration: Windows 10 with Outlook 2016 (from Office 365).