I am administrator of two ubuntu servers. On one of them, when I try to run a command (for instance irb1.9.1) from a package that is not installed, I get the following message:

The program 'irb1.9.1' is currently not installed.  You can install it by typing:

sudo apt-get install ruby1.9.1

On the other server, I get the following answer:

The program 'irb1.9.1' is currently not installed.  To run 'irb1.9.1' please ask your administrator to install the package 'ruby1.9.1'

I can sudo on both servers, so I don't understand how the first one knows I can install the package myself and shows me the command to run, while the second doesn't.

Where does the difference come from and how can I get the second server to give me the command like the first server?

Edit to answer Braiam's comment, apt-cache policy return the same on both servers:

$ apt-cache policy command-not-found

command-not-found:

  Installed: 0.3ubuntu7.1

  Candidate: 0.3ubuntu7.1

  Version table:

 *** 0.3ubuntu7.1 0

        500 http://dk.archive.ubuntu.com/ubuntu/ raring-updates/main amd64 Packages

        100 /var/lib/dpkg/status

     0.3ubuntu7 0

        500 http://dk.archive.ubuntu.com/ubuntu/ raring/main amd64 Packages