Às vezes, os pacotes são divididos em dois ou mais pacotes à medida que crescem muito ou arrastam muitas dependências. Isso pode ser o que aconteceu com a evolução. Eu verifiquei com
$ sudo dnf search evolution | egrep -i exchange
evolution-ews.x86_64 : Evolution extension for Exchange Web Services
evolution-mapi.i686 : Evolution extension for MS Exchange 2007 servers
evolution-mapi.x86_64 : Evolution extension for MS Exchange 2007 servers
que havia alguns pacotes extras disponíveis e com
$ sudo dnf install evolution
podemos ver que eles não são instalados por padrão. Pesquisando na web, finalmente encontrei uma página do gnome Conectando-se ao Exchange Servidores :
Choosing the right connector. Depending on the version of the Microsoft Exchange server that you would like to connect to it is required to make sure that an additional package is installed that provides this functionality.
For Microsoft Exchange 2007, 2010 and newer it is recommended to use the package evolution-ews.
Eu não sei porque você teve que reiniciar, em vez de simplesmente reiniciar o gnome. O pacote extra consiste principalmente em bibliotecas compartilhadas. Talvez a evolução tenha mantido um cache de quais bibliotecas foram instaladas e não tenha percebido as novas até a reinicialização.