Information complexity of query algorithms?
Yes, information theory is useful for proving lower bounds on the query complexity of problems in Computer Science.

Alexander Golynski gave a good example in his ground breaking paper titled "Cell probe lower bounds for succinct data structures", presented at SODA 2009. He uses information theory to prove a lower bound on query complexity, which in turns yields a lower bound in the bit-probe model for (succinct) data structures. You can download the paper from citeseer's cache or from ACM's repository. There does not seem to be a journal version of the article.

You might be interested also in the following articles from his bibliography, which also relate communication complexity with information theory:


Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and
Avi Wigderson. On data structures and asymmetric
communication complexity. Journal of Computer and
System Sciences, 57(1):37–49, 1998. [link]
Anna Gal and Peter Bro Miltersen. The cell probe
complexity of succinct data structures. In International
Colloquium on Automata, Languages and Programming,
pages 332–344, 2003. [link]