Comment 8 for bug 994309

A user contacted me on IRC with this issue, after some investigation it seems multiarch was never enabled on his system, possibly from installing or upgrading with an old/bad beta 12.04 image. Some further investigation revealed that he somehow had a "newer" version of dpkg than Precise ships, probably from a bad PPA or other such thing.

Please make sure this is not the case for you.