While doing spatial joins in QGIS you have to make sure that all your layers are in the same projection! Otherwise there is a high chance of wrong outputs.
In your example data the shapes PUP and PRG have no correct set CRS projection, while the other shapes are all in ETRS89/ETRS-TM32.
-> Reproject them by saving them with the correct CRS (right-click on layer -> save as with selected ETRS89/ETRS-TM32 projection).
-> Then load in the reprojected layers and merge them via the mmqgis function merge layers or through the function in the QGIS vector menu.
As soon as you have one single shape, you'll find the dissolve function in the vector menu.
If you still want to work in QGIS then you can do it by importing the shapefiles to GRASS and then exporting them back out again to shapefile. This should convert them both to polygon geometry and the merge will work.
Make sure the two layers are loaded into QGIS before you start.
To import into GRASS:
1. Load the GRASS plugin and the toolbars.
Open the plugin manager (Plugins --> Manage and Install Plugins) and search GRASS in the search bar, ensure that the checkbox is ticked. This should add a new GRASS toolbar to your QGIS window. If it doesn't right click on an empty part of the toolbar; this will bring up a list of toolbars, make sure that GRASS is ticked.
2. Create a GRASS workspace.
GRASS doesn't work with data in traditional folders like you would using QGIS with shapefiles. Instead it stores files in a database structure that you have to create before you can start. To do this (adapted from HERE):
In the GRASS toolbar, click on the "New Mapset" icon to bring up the MAPSET wizard. It should automatically create a default save folder in your user folder. Then click Next.
Choose to "create a new location" and call it something - for example 'Australia'. Click Next.
You then need to set the projection. Looking at your data some of it is in GDA94 EPSG: 4283 so I've used this. You can type "4283" into the search bar to filter the list. Click Next.
Leave the Default GRASS region alone and click Next.
Specify a name for the "mapset" -> I've called it 'Demo'. Click Next. Click Finish.
This should create your location and mapset and set it as the working directory. It should also load the GRASS tools (if it doesn't there is a toolbar button to load the tools). Your now ready to import the files into GRASS.
3. Load the data into GRASS
Open the GRASS tools and look at the Modules Tree. Open File Management -> Import Vector into GRASS and double click on v.in.ogr.qgis - Import Loaded Vector.
Select one of the files from the dropdown list. Give it a name in the box below - I've just copied the name of the shapefile to make it easier. Click Run. It might take a little while to do, particularly on your complex shapefile. When it's finished you can view it in QGIS by clicking View Output. Repeat this step for the other file.
When they're both in QGIS right click on them in the table of contents and select Save As. Save them to a regular folder on your harddrive in shapefile format.
Redo the join using the two new shapefiles that you've created. I've just tested it with the MMQGIS merge tool and it seems to work fine.
Best Answer
Having selected 'save vector layer as..' I stumbled upon the fact that one of the shapefiles I was attempting to merge included the 'z-dimension' as part of its geometry, whilst the other files didn't feature this. I re-saved all the shapefiles I need to merge, specifying in each case that the geometry type was 'polygon' and that the 'z-dimension' was unchecked, then re-ran the merge process - on this occasion successfully