As of Jan 2014 I think this is even more broken that it was a few months ago. No matter which search criteria I used, I could not get Google to return more than about 45 messages on my wife's account. There's no UI indication that the search results are incomplete.
I turned off both the "special boxes" and "conversation mode". Then I did a date search
Before:2014/1/1
Then I clicked the select all box - only 45 were returned and they were all checked, but I still checked Select All. THEN I could the subtle (old school) link to "Select all messages that match this search". Again, there's no UI indication, but when I clicked that I say "Loading ..." for a minute or two. Then the messages were archived.