I will preface my statement with the following:
I think that unions should be allowed and legal under any and all circumstances.
Now, for the counter-point. The state government gets a choice as to what labor laws to enforce (as per the constitution of the US) and my state (SC) is one where labor unions can form and dissolve whenever they want. In other states (http://www.nrtw.org/rtws.htm) labor unions can mandate membership by some crazy back-woods methods. In this environment, the union becomes the 'state' entity, pretending to be in it for the common worker, when in fact they run the whole thing like they are a second company which leeches off of the first. Read Animal Farm for a description of this trust effect. For you classic rock guys, this is an example of "Meet the new boss, same as the old boss". One key difference, as long as you work for a company, you can't quit the union. I guess another key difference is that the company pays you, while you pay the union.
There are greedy bastard companies out there, and unions should always be allowed to right them. Contracts such as these, however, are extremely far reaching, and never would have been signed in a right to work state (they would have just hired other people, a perfectly valid and moral course of action) instead. There are also greedy bastard workers out there, and they aren't the slightest bit less sleazy than the greedy bastard companies.
My opinion is that if the fed got out of this whole thing with regard to labor laws, you'd see a better balance of labor power vs company power, but until then, I moved to a right to work state. Seriously, that was one of my big points when I relocated from New York. I worked in a union shop, and got "grieved" for helping a 60 year old woman lift giant plastic pallets. Seriously.
If you don't like your job, get another one works to a point, and obviously organized labor works to prevent all companies from being run by greedy bastards, and keeps the happy happy joy joy nice guy companies from having to deal with labor (in a right to work state, anyway).
But like others have mentioned, this was understood by the company when they signed the contract. It's stupid, but correct by the letter of the paper they signed. Short termed thinking by the labor? Absolutely - and downright immoral if you ask me. Send the ship down to save my E36 M3ty $10/hour job for a few more weeks. It's not like the company didn't know this, though. They should have moved like I did.
/rant