Tem certeza de que a conta de serviço que você usa para o SQL Server corresponde à conta de usuário que você está usando para criptografar os arquivos? O EFS é tratado no sistema operacional e é transparente para o SQL Server.
Se esse for o caso, verifique as permissões gerais do NTFS, verifique se a conta de serviço tem controle total dos arquivos que você está tentando anexar. Pode estar afirmando o óbvio, mas você deve sempre verificar se há gás no tanque, não assuma!
Se você usa o SQL Server 2008 Enterprise, deve investigar o uso de Criptografia transparente de dados ( TDE) em vez de EFS, há melhor desempenho e é mais agradável de gerenciar.