I had the same problem - 'archive' was gone. I think I know what happened:
I had over 400 emails with a label marked 'Jobs'. When I select 'Jobs', the first 50 show on my screen. I previously selected 'All', but it apparently only select that first 50, and the archive option DID show up, but it looked like they were still there, so I tried it again. On the second try, 'archive' was gone.
To get it back, there's another step. Select 'all' once again, and notice that a link shows up saying something like "do you really want to mark all 427 conversations, or just the 50 on this page?" It's not very obvious, but you have to select that link.
Now the archive option shows up and seems to work. Oddly though, if I look at mail by selecting that label, they're still there. But, at least they're not in my Inbox, which is what I really wanted in the first place.
I guess I'm still trying to figure out the difference between 'archive' and 'delete'. I know I can still see both by selecting 'all email'.