This is an old thread but this is where Google leads with a search of the error message so I thought I'd add in my own findings.
This is a known bug and it will not be fixed (I have confirmed this with Esri support). The bug reference is NIM068106.
The composite locator will work if you connect to SDE as the owner of the locator, but not as another user. However, the current recommended best practice according to Creating an address locator is to use a locator stored in a folder on the file system:
However, for best practice and better geocoding performance, it is recommended that locators are stored in a file folder instead of a geocodebase (sic).
I've tested this in 10.2.2, 10.3, and 10.3.1.
Oh very interesting! As it turned out, it seems to work when we turn them into services and build the composite locator from the two other locator services. I don't know that everyone has that option though...
Thanks for the update though!