Wow that was an interesting morning. Thanks to everyone that identified the problem and posted a solution so quickly.

Oddly enough, a couple of rigs kept running - I can't think of anything about them that was different from the others. Though they also had the update and upgrade flags set to 1.

For me, just running 

sudo dpkg --configure -a

And then rebooting did the trick.