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):
…中耳炎なかなか治らなくってー、治ってはぶり返してぶり返しててー、病院通いも大変だし。 …my tympanitis just wouldn't get better, and every time it did it just kept coming back, and going to the hospital was a pain.
お母さんにも、あれなかなかわかってくれんかった。 I couldn't seem to get my mother to understand that either.
メールなかなか集まんないさー。 The e-mails don't really come in.
でもねー、なんかバスがなかなか来なかったりするじゃん… But there are times when the bus just won't show up, you know…
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:
あたし、でも、部屋が寒いとなかなか起きられないからさあ。 But for me, when the room's cold I can't seem to get out of bed.
最近さー、眼鏡がどこにあるかさえなかなか見つけられないぐらい、目が悪くなってきたんだけど。 Lately my eyes have gotten so bad I have trouble just finding where my glasses are.
連休の間だったから、あの、宿泊がなかなか取れなくって。 It was a long weekend, so, I couldn't really find a place to stay.
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:
だけどヤリイカの生がなかなか売ってないんですよ、魚屋さんに。 But it's hard to find fresh spear squid at the fish market.
そうだ、なかなか受けてくれる人いないもんな。 Right, there just aren't many people who would accept that.
緊張してるＡさんなんか、なかなか見れないから、見たかった。 It's not often you get to see A when he's nervous, so I wanted to see him.
ケーキって、１人で住んでると、なかなか食べないからさ。 Since cake, you know, isn't something you eat all that much when you're living alone.
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
any. In affirmative contexts,
any means universal quantification (expressed by the logical symbol
Any person would want to do that.
In negative contexts,
any means existential quantification (expressed by the logical symbol
I did not see any person in the building.
This sentence is the negation of:
I saw some person in the building.
and is not the negation of:
I saw every person in the building.
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.