Which version of Debian are you using? unstable? testing?
perhaps there is a bug registered against that package? If not, then it seems like there should be.
Here is the Debian web page where you can search the bug tracking system: http://www.debian.org/Bugs/
I have seen bugs within Debian unstable and testing, where invalid dependencies are specified.
Hope this helps