I am also having the same problem with the data shorcuts (Civil 3D 2013). I have tried the suggestions posted so far, but no luck. Any help would be appreciated.
I have the same problem using 2012 in that i would repeatedly get the error message requiring the dwg to be saved. I found that i couldnt create data shortcuts as my alignment was already linked to something in the dwg, In my case a profile & corridor. Once i deleted the corridor that it was linked to i could immediately create shortcuts.
It appears to have something to do with corridors and it's state when a save happens. Locking the layer the corridor is on appears to prevent the corridor from changing it's state based on the save action.
I'd experienced this error using Civil3D 2013. Previously my 'File Save' >> 'Save as:' Setting was set to AutoCAD 2010 (*.dwg). Whoever suggested problems with backwards compatibility was right, in my case. I changed this setting to AutoCAD 2013 (*.dwg) to match the year of the version I have and then I was able to create data shortcuts. I hate to forfeit compatibility for this though.