Con apt-pinning deberias poder bloquearlos, poniendo una prioridad
negativa. Del manual del apt_preferences:
P(riority) < 0
prevents the version from being installed
Así que en /etc/apt/preferences añades líneas como
Package: network-manager*
Pin: origin""
Pin-Priority: -1
Y... voliá!
# aptitude install network-manager-kde
No candidate version found for network-manager-kde
No candidate version found for network-manager-kde
No packages will be installed, upgraded, or removed.
0 packages upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
Marc Olivé