I'll vouch for batteries being a possible cause.
You would be surprised how much difference in battery length there is from some of the brands in relation to others.
I've found Duracell to be guilty from time to time of making a proper contact to the battery terminals. Not just on the eTrex, but also on other electrical gear.....
I use Energiser Ultra in mine successfully, if that gives you something to try and prove where the problem might lie.