Ambas as grafias, nenhuma e nem uma, estão correctas; os seus usos e funções é que são distintos.

A palavra nenhuma pode funcionar como determinante (i.e., antes de um nome) ou como pronome (i.e., em vez de um nome) indefinido, indicando negação (1)-(2), ausência (3)-(4) ou reforço de negação (5)-(6). As frases dos números ímpares correspondem a exemplos de nenhuma como determinante, as dos números pares correspondem a exemplos de nenhuma como pronome:
(1) Nenhuma pedra será removida.
(2) Juntou várias pedras mas nenhuma foi removida.

(3) Nenhuma sócia compareceu à festa.
(4) Convidou várias pessoas mas nenhuma compareceu à festa.

(5) Não tenho nenhuma vontade de sair hoje à noite.
(6) Experimentou várias blusas, mas não gostou de nenhuma.

Ainda em posição pré-nominal, e ligada à partícula de negação não, nenhuma pode ser equivalente ao indefinido uma:
(7) Ela não é nenhuma especialista na matéria, mas sabe o que diz.

Note-se que nas frases (1) e (3) nenhuma pode ser substituída por nem uma sem perda de sentido, contrariamente ao que sucede com a frase (5), que gera uma frase agramatical (5a):
(1a) Nem uma pedra será removida.
(3a) Nem uma das sócias compareceu à festa.
(5a) *Não tenho nem uma vontade de sair.

A palavra nenhuma, em posição pós-nominal, tem ainda uma função adjectival, reforçando a negação (5b). Neste contexto, nenhuma nunca pode ser substituída por nem uma, uma vez que tal substituição produz frases agramaticais como (5c):
(5b) Não tenho vontade nenhuma de sair.
(5c) *Não tenho vontade nem uma de sair.

A expressão nem uma pode também significar “nem mesmo uma”:
(8) Nem uma escavadora conseguiria remover esta pedra!

A frase de (8) significa que nem sequer uma escavadora conseguiria remover a pedra. Se nenhuma fosse utilizada em (8), o sentido seria outro: escavadora alguma conseguiria remover a pedra.

Notas

1. As respostas são datadas e escritas segundo a ortografia da norma europeia anterior ao Acordo Ortográfico de 1990.
2. A base do dicionário foi alterada a 1 de Abril de 2009, pelo que as referências em dúvidas anteriores a esta data podem não corresponder ao conteúdo actual.
3. As respostas sobre questões ortográficas são maioritariamente baseadas na norma ortográfica portuguesa de 1945, contendo as respostas mais recentes indicações sobre a ortografia antes e depois do Acordo Ortográfico de 1990.
4. A bibliografia utilizada está disponível aqui.