Mila Ready,
I had a look at your polygons in the attached zip file, and one of them turned out to contain intersections, which some geoprocessing tools like UNION can't handle. You'll need to repair the geometry of your polygons using the Repair Geometry Tool (ArcToolbox - Data Management Tools - Features Repair Geometry).
Secondly, prior to using the UNION tool, you need to specify the geographical extent of the new UNION-shapefiles you are creating. Right click ArcToolbox, open Environments, go to Processing Extents, set the Extent to "Union of Inputs", click OK. Then right click ArcToolbox again, and save the settings to default.
I tried it and it worked for me.
Note: If you have an ArcInfo license you can union as many polygon shapefiles as you like, but if you are using ArcView you can union only two at a time.
Hope this helps,
Eva Willerslev