Maverickmax,
I think I saw your problem here. You need a larger input capacitance, preferably 0.33-µF to 0.47-µF, than the output capacitance. Not making both the same of 0.1-µF because should your input is switched off, back-injection can kill 7805 in your design.
For 7805 to operate properly, you need to have at least 6.7Vrms to 7Vrms DC at the input of voltage regulator, preferably between 8 to 10Vrms to save on the use of a heatsink.
You also need to have at least 100mA to 250mA input current from your supply. Surprisingly, this is not specified in the datasheet. I personally tested a 7805 before and I remember clearly that you need to have input current above 100mA. If your battery is producing less than 250mAH, you are likely to have a problem with getting 5Vrms DC.