I got the same error message when trying to run 'Create Address Locator' today. No one is connected to my SDE database, and I can clearly connect through ArcCatalog to the reference featureclass. Please let me know if you hear anything.
What version of ArcGIS are you using? What database are you using? What version of SDE are you using? What are your database permissions and what type of connection are you using (direct connection or SDE connnection)?