The false readings are probably due to the extra exertion and will need to be filtered out in software. Two clues that help are that heartbeats don't suddenly double - so you can detect that spurious pulses are happening by the apparent jump in rate. Suggest reading about phase-locked-loops for the general approach for detecting a single-frequency signal buried in noise and harmonics.
There is a coil of transformer wire around a wooden pencil
Or maybe the device is telling you that you actually have a problem with your heart when you exercise.
I'm curious what is the part on right side, down the middle in round shape. The must be a ferrite, not necessary as big as in LW radio (10 cm) but as small as 1 cm installed vertically could bring up sensitivity 1000x times. Higher amplitude of signal at the input of the receiver, would lower requirements on next stage amplification, and consequently lower noise / interference susceptibility. I'd suggest not to use analogRead at all, after pulses get logic level right after OPA you can use comparator (or build-in atmega comparator) to father process signal by digital input, using input capture or external interrupt feature, in order to determine freq., pulse width, etc. Look here for some examples and libraries:http://interface.khm.de/index.php/lab/experiments/