I guess I've been in mathematics for far too long, and I tend to use the phrase "Not all is lost" as the negative of "All is lost".
To me the phrase "All is not lost" suggests that nothing is lost. It doesn't send the message I'm trying to give which is that "at least one thing is not lost".
What's your interpretation of the two phrases?
"All is not lost" does not suggest that nothing is lost. It is said to counter the statement or belief that everything is lost, despite appearances to the contrary. It expresses exactly the meaning you say you want to convey, i.e., "at least one thing is not lost."
"Not all is lost" is simply another, more emphatic way of saying the other. It emphasizes the negative and is a stronger counter to any contrary assertions that have been made.
That's the meat of the matter; now to the seasoning: No. 1 can also seem more optimistic, and may be used to suggest that victory is in fact possible. Similarly, No. 2 may sometimes be used in a bitter, pessimistic way to point up how little is left. It may mean that everything of importance has been lost, but there may still exist a consolation prize, meager though it may be. "Our house burned to the ground, but at least the dog house remained untouched," one might say ruefully. "You see? Not all is lost."
I'm with Robusto on this; "All is not lost" is the idiom used specifically to counter "All is lost". "All is lost" -> The situation is hopeless, we're doomed, there is nothing that can save us. "All is not lost" -> The situation can be salvaged somehow, we can make it through this, there's still hope.
"Not all is lost" (if I ever heard it used) would be the counter to "I've lost everything! It's all gone, I can't find any of it!" "Not all is lost; look, here's your paddleball, and here's your chair."
The usual sentence is "All is not lost", as in "there is still hope".
"Not all is lost" is either:
Hint: For purposes here, lose the idiom. As an adjective, "all," is "being or representing the entire or total number, amount, or quantity: All the windows are open. Deal all the cards; Constituting, being, or representing the total extent or the whole: all Christendom.
"All aspirin are not alike" (old Excedrin commercial), wherein conveys that no 2 aspirin are alike. "Not all aspirin are alike," conveys the meaning that "among all aspirin, some may be alike but some are certainly not." Endless appeal to idiomatic usage and common parlance will never resolve this.
I suppose the easiest way to specify your precise meaning would be to say either "Not everything is lost" or "Nothing is lost". But it lacks the poetry and simplicity of Milton's original.
Speaking as a programmer, this is something that has bothered me for a great deal of time as well. "All x is not y" would suggest that not a single x can be considered y, but indeed more often than not the speaker actually intends to convey that although some x are y, not all of them are.
Popular usage of "all is not" can be considered a strangely persistent idiomatic mistake, and is at best archaic. I don't ever hear phrases like "all is not lost" or "everything is not what it seems" outside of kitschy fiction and bad screenwriting.
To me, "All is not lost" means nothing is lost.
Not lost = 'unlost'
All is 'unlost' = nothing is lost
Or to use quantifiers for clarity: All is not lost = for all T, T is not lost = there is no such T that T is lost = nothing is lost
"All is not lost" is simply logically incorrect to convey what is meant, and "Not all is lost" is the correct way to express that meaning:
It is clear, to use a more specific example mentioned above, that "All windows are not closed" really means "All windows are open." A person from the U.S. would however almost always say this earlier phrase when he or she is instead trying to indicate that someone has failed to close one or more of the windows; that is, has left 'only some' open. And, as long as he or she is talking to USians, would be correctly understood, despite the mild illogic. Better to say "Not all windows are closed".
I'd be prepared to bet that if by some miracle, parents suddenly all began to teach their young children the logically correct way to combine negations with quantifiers, then 15 years later, the difficulties students have to understand theoretical calculus would disappear!
Replying to Gilles':
'Not all is lost' is both logically correct and has at least as much "..poetry and simplicity.." as "...Milton's original", namely 'All is not lost'. That Milton goofed logically several centuries ago gives his phrase no extra claim to some kind of actual 'correctness', the point being discussed. It is amusing however that this general logical error is made almost universally in US, and much less often elsewhere in the English-speaking world, even despite Disney and Hollywood. Milton didn't work for those guys!
