Well, when working with shapefiles, make sure you have write-access to the folder in which they are stored and all the individual files (such as .shp, .dbf, etc.) that make up the shapefile. The settings you mentioned for versioned and non-versioned editing do not apply to shapefiles; they are only used with ArcSDE geodatabases.
Also, try adding the shapefiles to a blank map document to see if there is something in the map that is causing this.