It shouldn't be necessary to specify this dependency here. The ${shlibs:Depends} stanza causes dpkg to add the dependency automatically, since you depend on libtokyocabinet-dev and use it in the build. Try removing it? This would have the added bonus of not requiring you to specify versions (8 | 9), making this more future-proof.