Hi,
dlocate now has two new options: -lsbin, and -lsman[1]. So, here is an updated 
zsh completion proposal:
arno.
[1]: http://packages.qa.debian.org/d/dlocate/news/20071120T151702Z.html
--- /home/arno/_dlocate	2007-11-21 19:11:45.000000000 +0100
+++ _dlocate	2007-11-21 19:12:37.000000000 +0100
@@ -13,6 +13,8 @@
 	'-du[du -sck of all files in package]' \
         '-conf[list conffiles in package]' \
 	'-lsconf[ls -ldF of conffiles in package]' \
+	'-lsman[list man pages in package]' \
+	'-lsbin[list executable files in package]' \
 	'-md5sum[list md5sums (if any) of package]' \
 	'-md5check[check md5sums (if any) of package]' \
 	'-man[list man pages (if any) of package]' \
Attachment:
signature.asc
Description: Digital signature