Recommends is wrong for metapackages because it gets upgrades very wrong. This is why it is used very marginally.
Couldn't this get fixed if Depends: network-manager-gnome (>= 0.9.4) was replaced with Recommends: network-manager-gnome Breaks: network-manager-gnome (<< 0.9.4)