chef-solo binary removed after chef upgrade, returns on reinstall

I'm setting up a server configuration for ubuntu trusty that must be compatible with our node configuration using chef-solo.

This is in AWS EC2, and the base node is from the official ubuntu repo in https://cloud-images.ubuntu.com/locator/ec2/

This base image already contains chef v11.6.2-1.ubuntu.13.04, with the chef-solo binary ready to use. Nice.

But on upgrading the chef package to v11.8.2-2, the chef-solo binary just disappear, along with some other chef binaries. If I remove and install again this same package (or reinstall it), they appear again.

$ dpkg -s chef | grep ^Version
Version: 11.6.2-1.ubuntu.13.04
$ ls -1 /usr/bin | grep chef
chef-apply
chef-client
chef-shell
chef-solo

$ sudo aptitude upgrade chef -y
$ dpkg -s chef | grep ^Version
Version: 11.8.2-2
$ ls /usr/bin | grep chef
chef-service-manager
chef-zero

$ sudo aptitude reinstall chef -y
$ dpkg -s chef | grep ^Version
Version: 11.8.2-2
$ ls /usr/bin | grep chef
chef-apply
chef-client
chef-service-manager
chef-shell
chef-solo
chef-zero

And the dependencies removed and then reinstalled are exactly the same.

$ sudo aptitude remove chef
The following packages will be REMOVED:  
  chef chef-zero{u} erubis{u} ohai{u} ruby-diff-lcs{u} ruby-erubis{u} ruby-hashie{u} ruby-highline{u} ruby-ipaddress{u} ruby-json{u} ruby-mime-types{u} ruby-mixlib-authentication{u} ruby-mixlib-cli{u} ruby-mixlib-config{u} 
  ruby-mixlib-log{u} ruby-mixlib-shellout{u} ruby-net-ssh{u} ruby-net-ssh-gateway{u} ruby-net-ssh-multi{u} ruby-rack{u} ruby-rest-client{u} ruby-sigar{u} ruby-systemu{u} ruby-yajl{u} 
0 packages upgraded, 0 newly installed, 24 to remove and 0 not upgraded.
Need to get 0 B of archives. After unpacking 8,363 kB will be freed.

$ sudo aptitude install chef
The following NEW packages will be installed:
  chef chef-zero{a} erubis{a} ohai{a} ruby-diff-lcs{a} ruby-erubis{a} ruby-hashie{a} ruby-highline{a} ruby-ipaddress{a} ruby-json{a} ruby-mime-types{a} ruby-mixlib-authentication{a} ruby-mixlib-cli{a} ruby-mixlib-config{a} 
  ruby-mixlib-log{a} ruby-mixlib-shellout{a} ruby-net-ssh{a} ruby-net-ssh-gateway{a} ruby-net-ssh-multi{a} ruby-rack{a} ruby-rest-client{a} ruby-sigar{a} ruby-systemu{a} ruby-yajl{a} 
0 packages upgraded, 24 newly installed, 0 to remove and 0 not upgraded.
Need to get 0 B/1,278 kB of archives. After unpacking 8,363 kB will be used.

The only difference in the binaries installed is that on v11.6 they are links from /usr/bin to /opt/chef/bin, but in v11.8 the binaries are in /usr/bin.

This is quite inconvenient, as if I do the upgrade on the first chef run, I can no longer run chef without manual intervention.

Can anyone help me understand what is going on, and how can I get this package upgraded in chef without running into this problem?

P.S.: I know I can stay with v11.6 holding this version, but this is not what I'm asking.