Where are you connecting your voltmeter to measure the voltage from the 7805? Can you post a picture of your actual circui (camera phone?) showing the circuit and how you are connecting the volt meter?
The 7805 is about as bullet proof as things get, so as Jack said, if wired in correctly what you are seeing should never occur.
Do you have a second 7805? If so, if you use it to replace the first one in the circuit do you see the exact same behavior?