/var/lib/dpkg/available is not updated when packages are installed

This is a fresh install from a Xenial daily today. All I've done post-install is configure networking, add a ppa, update the apt-cache and dist-upgrade. Then I installed MAAS to the machine.

Now I am running a script we have to configure MAAS for Certification and discovered a part that does a dpkg query is failing. On further digging, it looks like dpkg is not able to properly query the database.

For example:

bladernr@critical-maas:~$ dpkg -l |grep vim
ii vim 2:7.4.826-1ubuntu3 amd64 Vi IMproved - enhanced vi editor
ii vim-common 2:7.4.826-1ubuntu3 amd64 Vi IMproved - Common files
ii vim-runtime 2:7.4.826-1ubuntu3 all Vi IMproved - Runtime files
ii vim-tiny 2:7.4.826-1ubuntu3 amd64 Vi IMproved - enhanced vi editor - compact

dpkg tells me I have vim installed. Now I try this:

bladernr@critical-maas:~$ dpkg -p vim
dpkg-query: package 'vim' is not available
Use dpkg --info (= dpkg-deb --info) to examine archive files,
and dpkg --contents (= dpkg-deb --contents) to list their contents.

man says this:

-p, --print-avail package-name...
                  Display details about package-name, as found in
                  /var/lib/dpkg/available. Users of APT-based frontends
                  should use apt-cache show package-name instead.

installing packages does not update this file, apparently. This seems to be a regression as this works fine in Trusty.

Example: vim was installed via apt-get on Trusty here and dpkg -p works:
bladernr@sulaco:~$ dpkg -p vim
Package: vim
Priority: optional
Section: editors
Installed-Size: 2185
Maintainer: Ubuntu Developers <email address hidden>
Architecture: amd64
Version: 2:7.4.052-1ubuntu3
Provides: editor
Depends: vim-common (= 2:7.4.052-1ubuntu3), vim-runtime (= 2:7.4.052-1ubuntu3), libacl1 (>= 2.2.51-8), libc6 (>= 2.15), libgpm2 (>= 1.20.4), libpython2.7 (>= 2.7), libselinux1 (>= 1.32), libtinfo5
Suggests: ctags, vim-doc, vim-scripts
Size: 955616
Description: Vi IMproved - enhanced vi editor
 Vim is an almost compatible version of the UNIX editor Vi.
 .
 Many new features have been added: multi level undo, syntax
 highlighting, command line history, on-line help, filename
 completion, block operations, folding, Unicode support, etc.
 .
 This package contains a version of vim compiled with a rather
 standard set of features. This package does not provide a GUI
 version of Vim. See the other vim-* packages if you need more
 (or less).
Homepage: http://www.vim.org/
Original-Maintainer: Debian Vim Maintainers <email address hidden>

ProblemType: Bug
DistroRelease: Ubuntu 16.04
Package: dpkg 1.18.4ubuntu1
ProcVersionSignature: Ubuntu 4.4.0-2.16-generic 4.4.0
Uname: Linux 4.4.0-2-generic x86_64
ApportVersion: 2.19.4-0ubuntu2
Architecture: amd64
Date: Thu Feb 11 18:41:56 2016
InstallationDate: Installed on 2016-02-10 (1 days ago)
InstallationMedia: Ubuntu 16.04 LTS "Xenial Xerus" - Alpha amd64 (20160210)
ProcEnviron:
 TERM=xterm
 PATH=(custom, no user)
 XDG_RUNTIME_DIR=<set>
 LANG=en_US.UTF-8
 SHELL=/bin/bash
SourcePackage: dpkg
UpgradeStatus: No upgrade log present (probably fresh install)