I'd have to say it sounds a lot like a bad connection, either positive, or negative. it could also be a bad ground cable(i've had that one happen before)
also, have you had the battery load tested? i know you said it was replaced but believe me it doesn't mean a thing.
back when i used to work on cars for a living, i'd see a brand new battery fail within a day every once in a while. it seemed like it was always....well i don't want to name any names but they were made by a company that started with "E" and we used to refer to them as ex-crement
(god am i glad that i work on diesels now
)
just for grins, get a pair of jumper cables, clamp one end to the starter stud nut on the backside of the bellhousing, and the other end on the negative post.
if it starts, you know you have a bad ground