I know you said the plugs are fairly new but it would be worth taking them out and giving them a quick cleaning. I have seen it work for 2 cars last week. Also in the cold weather last winter I was unable to start mine unless it was getting a jump from another car, it had a brand new battery, after changing plugs I never had another problem. Ryan