It sounds to me that you have faulty wiring or a a faulty connection. Post a schematic and a few photos of your setup. Confirm that you have connected the Avcc pin of the atmega328p to +5V, even if you are not using the ADC?
PS - also connect a 0.1uF ceramic capacitor directly between the Vcc and ground pins of the atmega328p