It's a little bit too easy to accidentally remove All Inboxes from Favorites. All you have to do is click and drag it off the sidebar, and "poof" it disappears. I've seen it happen before and it can really torment the user. One time, I completely reset the Mail preferences before discovering the hidden Favorites > + button. Glad you all figured it out.