Remoted with @tom-langenfeld and we were able to fix the issue.
He was running Ubuntu 15.10, and the Ondrej repo would install, but there were no PHP packages for wily apparently. Updated to 16.04 and had to run a few tricks to get mysql working, but once all was working, everything appears to be running properly now.