This error usually related to having the data frame coordinate system different from the layer coordinate system. Try opening a new blank map document, add the layers, and then perform the clip. You might also check to see if the coordinate systems are different between the layers.
