I second the battery connections theory. I had exactly the same sort of thing going on with a new battery, and got randomly stranded a couple times. My connections were tight, but there was some corrosion, and some scorched looking stuff that, after brushing it off and re-tightening, hasn't been a problem since.
Ben