Libboost_Program_Options. So Not Found Even Though the Package Is Installed

I'm on Ubuntu 15.10. I have packages libboost-program-options1.58-dev, libboost-all-dev installed, but the library itself is apparently not present:

$ sudo find / -name libboost_program_options

Only boost libs that are present are:

$ l /usr/lib/x86_64-linux-gnu/ | grep libboost                                                                                                                                                    
-rw-r--r--   1 root root   67K Oct 14 15:53 libboost_date_time.so.1.58.0
-rw-r--r--   1 root root   95K Oct 14 15:53 libboost_filesystem.so.1.58.0
-rw-r--r--   1 root root   95K Oct 14 15:53 libboost_iostreams.so.1.58.0
-rw-r--r--   1 root root   15K Oct 14 15:53 libboost_system.so.1.58.0

I get following error with some programs:

$ vera++
vera++: error while loading shared libraries: libboost_program_options.so.1.58.0: cannot open shared object file: No such  file or directory
FAIL

What is wrong with the packages?

UPDATE:

 $ apt-cache policy libboost1.58-dev                                 
libboost1.58-dev:
  Installed: 1.58.0+dfsg-3.1ubuntu1
  Candidate: 1.58.0+dfsg-3.1ubuntu1
  Version table:
 *** 1.58.0+dfsg-3.1ubuntu1 0
        500  wily/main amd64 Packages
        100 /var/lib/dpkg/status

 $ sudo apt-get install libboost-program-options-dev                 
Reading package lists... Done
Building dependency tree       
Reading state information... Done
libboost-program-options-dev is already the newest version.
0 upgraded, 0 newly installed, 0 to remove and 13 not upgraded.

 $ dpkg -L libboost-program-options1.58-dev                          [14:12:23]
/.
/usr
/usr/share
/usr/share/doc
/usr/share/doc/libboost-program-options1.58-dev
/usr/share/doc/libboost-program-options1.58-dev/copyright
/usr/lib
/usr/lib/x86_64-linux-gnu
/usr/lib/x86_64-linux-gnu/libboost_program_options.a
/usr/share/doc/libboost-program-options1.58-dev/changelog.Debian.gz
/usr/lib/x86_64-linux-gnu/libboost_program_options.so

 $ cat /usr/lib/x86_64-linux-gnu/libboost_program_options.so         [14:13:01]
cat: /usr/lib/x86_64-linux-gnu/libboost_program_options.so: No such file or directory