I second the call for a ground check. I was having all sorts of intermittent starting problems (just a click) that were finally traced to a rusty ground connection point (solved with sandpaper). It could also be time to replace the battery cables themselves. I have seen a cable lose a couple volts in less than a foot of bad battery cable, but from the outside the cable looked fine. Finally you might want to check the specific gravity of the battery juice to make sure it really has a good charge on it, volt meters are just about useless for determining the state of charge of a battery. The fact that you were having battery problems before makes it seem unlikely that your problem is with the starter.