Hello,
Make sure that you have write permissions for the files and the folder that the shapefile is in (that's one reason why Define Projection would not work). Close ArcMap if it's open (we want to make sure that the shapefile isn't locked by being in use somewhere).
Use the Define Projection tool in ArcToolbox. You will probably get a warning that the shapefile already has a coordinate system. You can ignore the warning. Set the coordinate system to the ETRS 1989 geographic coordinate system. It's under geographic coordinate systems, Europe. In ArcCatalog, refresh the folder by selecting it and hitting F5. Now try adding the shapefile to a new ArcMap with your administrative boundaries.
Melita