• I'd just check using SSMS for the ADsDSOObject in the provider under the LinkedServers Providers node to see if the provider is installed.

    What is the security set on the ADSI linked server?