Linear regulator (L7805CV) outputting 5.8V
I think you may have already checked for most of the topics in the list bellow. However, I have tried to make an exhaustive list that will surely help others arriving this question.

The usual suspects when dealing with issues with the 78xx standard linear regulators:


The output may be oscillating, which may be difficult to verify if you only have a digital multimeter at hand. Check, if possible, with an oscilloscope. Possible culprits:

Follow the manufacturer's recommendations for input and output capacitors. Not all capacitor technologies (Aluminum, Tantalum, ceramic) are allowed. Not all values are allowed. Check also the range of input/output capacitance for stable operation. There is usually at least one section in the datasheet devoted to stability.
Check that you are respecting the minimum/maximum input voltage for the regulator. Minimum input voltage could be as high as Vout + 2.5V, depending on the device. Maximum input voltage varies hugely among different devices. Again, check the datasheet.
Check that a minimum load current is required from the regulator. Some devices are happy with very low load current (&lt;1mA), however, many 78xx devices will require a minimum load current for stable operation.

If the output voltage is higher that it should be:

Check that the ground is not being "pulled up". Most 78xx devices can effectively work with a "virtual ground", that is, if you insert a resistance from the common return to ground, the reference voltage and the output voltage will both rise by V=R*I, being R the common path resistance to ground and I the quiescent current plus load current.
The device may be broken, faulty or a counterfeit. Simply check with another sample, even best if you can try a sample from another batch.

If the output voltage is lower that it should be:

Check that you are respecting the minimum voltage drop required by the regulator. Check the datasheet. Some non LDO devices may require the input voltage to be up to several volts higher than the specified output voltage.

Check your measurement devices. If possible, try more than one DMM. Check your batteries. Even better, check the signals with an oscilloscope.
Check your power supply: real output voltage, noise, current capabilities...
Check your connections. Twice. Lots of the electronic issues during the prototyping phase can be traced down to bad connections or mafunctioning breadboards.
Check the pinout of your device. Make sure you are wiring correctly the ground, reference and output connections.
Beware of shorting the input of your voltage regulator. Many of the 78xx devices cannot withstand a "short" in the input capacitor while the output capacitor is still charged. This will usually damage permanently your device, totally or partially (even worse), which could explaing the strange behaviour of the device from than point on.