DEB: "Provides:" field ignored

I need to replace a package with a custom one, which gets its own name (foo-origpackage). To allow it to be used as drop-in replacement, I added the Provides: origpackage line to the control file. apt-cache show foo-origpackage lists the "Provides" entry just fine. However, when I want to install a file depending on origpackage, it fails ("Package origpackage not installed").

Is there some distinction between "real" and virtual packages I'm missing?

EDIT:

To be precise, what I want to replace is xen-utils-common for Squeeze. My tao-xen-utils-common has the following control file:

Source: tao-xen-utils-common
Section: kernel
Priority: optional
Maintainer: Creshal <[email protected]>
Build-Depends: debhelper
Standards-Version: 3.8.0
Homepage: http://tao.at

Package: tao-xen-utils-common
Architecture: all
Depends: gawk, lsb-base, udev, xenstore-utils, tao-firewall
Provides: xen-utils-common
Conflicts: xen-utils-common
Replaces: xen-utils-common
Description: Xen administrative tools - common files (modified)
 The userspace tools to manage a system virtualized through the Xen virtual
 machine monitor.
 Modified for use with TAO Firewall.

Installing xen-utils-4.0 fails, however:

foo@bar# apt-cache showpkg tao-xen-utils-common
Package: tao-xen-utils-common
Versions: 
4.0.0-1tao1 (/var/lib/apt/lists/repo.tao.at_dists_stable_main_binary-amd64_Packages) (/var/lib/dpkg/status)
 Description Language: 
                 File: /var/lib/apt/lists/repo.tao.at_dists_stable_main_binary-amd64_Packages
                  MD5: 7c2503f563fca13b33b4eb3cbcb3c129


Reverse Depends: 
  tao-firewall,tao-xen-utils-common
  tao-firewall,tao-xen-utils-common
Dependencies: 
4.0.0-1tao1 - gawk (0 (null)) lsb-base (0 (null)) udev (0 (null)) xenstore-utils (0 (null)) tao-firewall (0 (null)) xen-utils-common (0 (null)) xen-utils-common (0 (null)) 
Provides: 
4.0.0-1tao1 - xen-utils-common 
Reverse Provides: 


foo@bar# apt-get install xen-utils-4.0
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following extra packages will be installed:
  xen-utils-common
Suggested packages:
  xen-docs-4.0
The following packages will be REMOVED:
  tao-xen-utils-common
The following NEW packages will be installed:
  xen-utils-4.0 xen-utils-common

Edit:

foo@bar# apt-cache policy xen-utils-4.0
xen-utils-4.0:
  Installed: (none)
  Candidate: 4.0.1-4
  Version table:
     4.0.1-4 0
        500 http://ftp.at.debian.org/debian/ stable/main amd64 Packages
     4.0.1-4 0
        500 http://security.debian.org/ stable/updates/main amd64 Packages

I spent quite some time investigating this same issue and I reached the conclusion that the the "Provides" is ignored because xen-utils-4.0 has a versioned "Depends" on xen-utils-common.

Quoting the Debian Policy Manual:

A Provides field may not contain version numbers, and the version number of the concrete package which provides a particular virtual package will not be considered when considering a dependency on or conflict with the virtual package name.

If the Depends were unversioned, the provides would have been satisfied, however a Provides, which is always unversioned, can never satisfy a versioned Depends.

Unfortunately, I do not have a solution apart from what you have already proposed: keeping the same package name and having a higher version number.

The section of the Debian Policy Manual quoted in @cavedon's answer is still unchanged, but outdated. Since dpkg 1.17.11 setting a version on a provided package is possible. From the changelog:

• Add versioned Provides support:
  • Add a new dpkg --assert-versioned-provides command.
  • Packages can provide a specific version, “virtual (= 1.0)” which will be honored, previously it would just be accepted when parsing.
  • Non-versioned virtual packages will not satisfy versioned dependencies.
  • Versioned virtual packages will satisfy non-versioned dependencies. Based on skeletal code by Ben Collins . Closes: #7330, #24934, #112131, #134582, #180316

So to solve the original example, in the control file you add a line

Version: *version*

(replacing *version* with the actual version) and replace the line

Provides: xen-utils-common

with

Provides: xen-utils-common (= ${binary:Version})