SOLUTION: Guys don't waste your time. I had this exact problem but I tried using command + alt + r during boot up. Hold it till you see the globe pop up and let it do its thing and that should fix the problem (at least it did for me). Then you can install without problems. Good luck!
If didnt work buy an external hard disk and connect it to your mac and go to disk utilities and go to ur old hard drive then go to restore ,if the sorce is your hard disk name so thats ok usually its macintosh hd and in the other side destination grab the new hard disk, the new hard disk is gonna erase and copy the old hard disk so you are gonna have a back up ,when it finishes go to ur old drive theb click erase it will work ,you must put it on macOS (journaled) or the first option then just do the same on the first and it will work.
Good luck