This might sound a bit too simple, but I had exactly the same problem using the Thunderbird email program.
No matter what I tried, the Internet Email icon remained greyed out and the status message just said 'Waiting for subsystem to start'.
After a lot of advice on various possible solutions, I tried the following:
Click on the Internet Email icon to select it. Then click the 'Terminate' button. Now click the 'Start' button to restart the provider.
It worked for me!