Thilo acertou a diferença com precisão...
COUNT( column_name ) pode retornar um número menor que COUNT( * ) if column_name pode ser NULL . No entanto, se eu puder responder à sua pergunta de um ângulo um pouco diferente, já que você parece estar se concentrando no desempenho.
Primeiro, observe que a emissão de
SELECT COUNT(*) FROM table; irá potencialmente bloquear os escritores, e também será bloqueado por outros leitores/gravadores a menos que você tenha alterado o nível de isolamento (o reflexo tende a ser WITH (NOLOCK) mas estou vendo um número promissor de pessoas finalmente começando a acreditar no RCSI). O que significa que enquanto você está lendo os dados para obter sua contagem "precisa", todas essas solicitações DML estão se acumulando e, quando você finalmente libera todos os seus bloqueios, as comportas se abrem, um monte de inserir/atualizar/excluir atividade acontece, e lá se vai sua contagem "precisa". Se você precisar de uma contagem de linhas absolutamente consistente e precisa (mesmo que seja válida apenas para o número de milissegundos necessários para retornar o número para você), então
SELECT COUNT( * ) é sua única escolha. Por outro lado, se você estiver tentando obter uma estimativa de 99,9% de precisão, ficará muito melhor com uma consulta como esta:
SELECT row_count = SUM(row_count)
FROM sys.dm_db_partition_stats
WHERE [object_id] = OBJECT_ID('dbo.Table')
AND index_id IN (0,1);
(A
SUM existe para contabilizar tabelas particionadas - se você não estiver usando particionamento de tabela, pode deixá-lo de fora.) Este DMV mantém contagens de linhas precisas para tabelas com exceção de linhas que estão participando de transações no momento - e essas mesmas transações são as que farão seu
SELECT COUNT espera da consulta (e, finalmente, torná-la imprecisa antes que você tenha tempo de lê-la). Mas, caso contrário, isso levará a uma resposta muito mais rápida do que a consulta que você propõe e não menos precisa do que usar WITH (NOLOCK) . 
