This is a great question. This might be intended behavior rather than a bug. Mission Control seems to have blended both the old Expose and the old Spaces. With that in mind, launching a new app Full Screen places it on its own desktop. When you get to Mission Control you see it placed to the right of the original, empty Desktop. Open a second app Full Screen and that will place it again on its own desktop, next to the first Full Screen app you opened.
Just like the Home Screens in iOS and the old Spaces, it would seem that Apple intends these desktops to stay, space-wise, in the same place. Mail is "to the left" of Safari if I opened Safari after opening Mail. I agree that this spatial notion collides with our pre-conceived understanding of the switcher. That is same reason why hiding is disabled for Full Screen apps (pressing ⌘+H will not hide a Full Screen app).
If everything is full screen, the concept of hiding becomes less relevant. I think back to the older versions of Mac OS, where you had stacks upon stacks of windows. Hiding an app like Adobe Photoshop (and all of its many opened child windows for each one of my many opened images) made sense. If such window "stacking" is spatially not there (because those Full Screen apps are now side-by-side, they're not really stacked) then it almost makes sense that it doesn't work.
Having said all of that, I could not agree more that Lion has completely messed around with the workflow of many old-time Mac users. I do not necessarily agree with Apple's decisions here, I am just trying to play advocate and see if this one in particular has some explanation that makes sense. Hope this helps.
This article at TidBITS mentions a new feature in Lion called Automatic Termination. I was not aware of this feature. I wonder if the behavior that is being experienced by this question's author is related to this.