WWWJDIC defines なかなか (with negative verb) as by no means
But shouldn't it have been considerably ?
By no means means 100% not
considerably means like 85% not
So does なかなか (with negative verb) bends more towards by no means or considerably?
Ah, なかなか. How often you frustrate my attempts to translate you! 「なかなか」はなかなか翻訳しづらいですね。
I will leave the discussion of inter-language correspondences to the professionals and attempt to educe a definition. For my example sentences, I will use the Chakoshi corpus from Purdue (searchable here, but the interface leaves much to be desired).
First, with non-potential verbs (these are from the conversational corpus, so there are some really informal contractions here):
The first conclusion we can draw from these examples is that they imply the passage of time. That is, a particular state (defined by the negative verb) continues over some length of time.
The use of なかなか can also imply an expectation on the part of the speaker. In the sentences above, なかなか hints that the speaker waited for and expected something to happen (the tympanitis to get better, the e-mail to accumulate, etc), but after some time passed, the expected result still had not come.
These two implications are present in sentences with potential verbs as well:
With potential verbs, なかなか implies that the speaker put forth a good deal of effort (over a length of time) but was still not rewarded with the expected result, or that the speaker achieved the desired result only with difficulty.
A sub-category of なかなか deals with existence or frequency:
This use of なかなか merely implies that the action does not happen all that much or only rarely. The implication of expectation is weakened or entirely absent in this use.
As mentioned by others, there is no nice English translation for なかなか that works all the time, so it has to be treated on a case-by-case basis. I hope the examples and explanations here help you decipher なかなか the next time you see it paired with a negative.
Elaborating on Amanda's comment, it is very often that one word in some language has to be translated into two different words in another language depending on the polarity (negation or affirmative) of the sentence. To give you an example in English, consider the word
In negative contexts,
This sentence is the negation of:
and is not the negation of:
It might be possible to subsume these two meanings under a single meaning depending on the linguistic analysis you take. But it is also true that different languages use different words to make different distinctions. That may help you imagine why it is like what you asked.