SOLVED: Finally, I got my new email notification to work, as well as the icon. It doesn't make sense, but out of desperation I turned Mail and Outlook 2013 OFF in my Action Center. Then, everything started working! So maybe there was a conflict between the app and the Action Center? IDK, but I'm happy to see my email icon change when new mail arrives, and to hear the sound.