Well, I had a similar problem, but it was different in that I was not able re-install an OS. It ended up being an SSD failure (thank fuck for Time Machine).
When you booted into recovery (CMD+R) where you able to run a disk check? Did that say everything was okay?