For anyone searching this in Outlook 2010 and saying, I already did that and it isn't working, you aren't crazy. I had to right click on the "Arrange By" bar and then click "View Settings". This will open up the Advanced View Settings, and from here click on "Columns". You will need to then find "Icon" in the Available Columns Field, highlight/click on it, and then click "Add ->" to move it to the "Show these columns in this order" Field. Click OK and voila, Envelope Icons are back. 

That doesn't make it display in the system tray like it used to so it was staring me in the face. I still have to click on the hidden icons arrow to check for an envelope, so I may as well look at my Inbox.