An alternative to changing the provides header, can be to specify both names. Ie something like
Provides: NetworkManager network-manager Happy hacking, -- Petter Reinholdtsen -- To UNSUBSCRIBE, email to debian-bugs-dist-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org
