Closely related to skimming - can't do an equivalent of a binary search on it, if you have to jump back 100 pages to look at something you saw. I have a recipe book with 1000 recipes on the Kindle and it's a total nightmare to use. A paper copy is so much more usable.
This doesn't seem un-fixable, though. Something like dragging the page indicator backwards/forwards would help, or mirroring the iPod's wheel gesture to move back-forth more quickly. Spin two fingers for chapters, or something.
The issue is not the interface, it's the speed--an e-ink display is naturally slower right now. It is a real problem but one due to technology rather than UI.
Coincidentally, on my 3rd-generation Kindle (the one with the keyboard), you can jump by chapters using the left and right arrow keys. This ameliorates going back in most books.
Also, Kindles have a nice text search which I've found useful on several occasions. This has also helped somewhat, although it's still lacking overall.
Ultimately, I would not want any non-linear books on my Kindle either--I'll stick to pdfs and actual textbooks for now.
This doesn't seem un-fixable, though. Something like dragging the page indicator backwards/forwards would help, or mirroring the iPod's wheel gesture to move back-forth more quickly. Spin two fingers for chapters, or something.