Tokyo Cabinet is more complete and stable, Kyoto is too fresh yet (today is Dec 8 2010) and has some issues. Kyoto, written in C++, is (much) more simple than Tokyo (written in C), but this simplicity let some gap. The performance of Kyoto is a little bit worse than Tokyo, but works better with threads (at least the documentation promises that).
From the official documentation:
<< In 2007, Tokyo Cabinet was developed as the successor to QDBM on the following purposes. They were achieved and Tokyo Cabinet could replace conventional DBM products.
(...)
In 2009, Kyoto Cabinet was developed as another successor to QDBM. Compared with the sibling product (Tokyo Cabinet), the following advantages were pursued. However, the performance of Tokyo Cabinet is higher than Kyoto Cabinet, at least in single thread operations. >>
I used both, but I still prefer Tokyo, because I had a problem with Kyoto: In Kyoto Cabinet Database using File Hash Database, how can avoid file size increasing? and no one was able to help me. I still don't know how to solve that.
In my personal experience, I found Kyoto easier to compile and install, and also easier to use. I had big problems with Tokyo library dependences and problems to link the native library with the Java interface. With Kyoto everything was good and works fine in the first attempt. But, as I said before, I feel more control over the database using Tokyo.