package claims to provide xmodmap, but doesn't

This is not only true for xmodmap but many other clients too. This package
contains no clients at all.

xfonts-utils is another package which contains nothing.

Uhm?

daniels@ephemera:~/canonical/mesa/mesa-6.3.1.1% dpkg -L xfonts-utils
/.
/usr
/usr/bin
/usr/bin/update-fonts-alias
/usr/bin/update-fonts-dir
/usr/bin/update-fonts-scale
/usr/bin/mkfontdir
/usr/bin/mkfontscale
/usr/share
/usr/share/man
/usr/share/man/man1
/usr/share/man/man1/mkfontdir.1.gz
/usr/share/man/man1/mkfontscale.1.gz
/usr/share/man/man8
/usr/share/man/man8/update-fonts-scale.8.gz
/usr/share/man/man8/update-fonts-alias.8.gz
/usr/share/man/man8/update-fonts-dir.8.gz
/usr/share/doc
/usr/share/doc/xfonts-utils
/usr/share/doc/xfonts-utils/copyright
/usr/share/doc/xfonts-utils/changelog.Debian.gz

daniels@ephemera:~/canonical/mesa/mesa-6.3.1.1% dpkg -l xfonts-utils
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Installed/Config-files/Unpacked/Failed-config/Half-installed
|/ Err?=(none)/Hold/Reinst-required/X=both-problems (Status,Err: uppercase=bad)
||/ Name Version Description
+++-=========================-=========================-==================================================================
ii xfonts-utils 6.8.2.1-3 utilities for X font
packages

You're right, sorry from the bug spam. The empty xfonts-utils is a local problem.

fixed in breezy