fungus:
No, it's an AVR chip problem.
Not necessarily.
The internal clock varies with voltage.
Yup. By a very very tiny amount.
A different power supply will run the chip at a different clock speed.
Yup. By a very very very tiny amount.
To fix it you need an external crystal.
If that's the case, the power supply is irrelevant; the target just needs to be tuned.