The input capacitor is essential, especially if you are going to change from one 7805 to another.
I had the same problem - 7805 giving out 6V. Put a 47uF on the front end and all was hunky dory. Looking at the Vin signal, there was a lot of ac, even though I was running from a bench power supply. 47uF removed this.
Also, time for dumb question of the week: what was the output of your 5V power supply.....?
If it was only 5V then the 7805 will not have had enough drop across it to regulate. If it was >7V then it would have been OK.
6 batteries will generate your >7V