Looks like I'm chiming in a bit late, but when my car started doing this, the first thing i did was fully clean all the contacts. I disconnected the battery, climbed under the car, unhooked the cable coming from the battery and used a brass brush and scrubbed until the contact was shiny. I reconnected the cable and my car has not hiccuped at start for over 2 years. Looks like you've already replaced the starter. Maybe this might help other readers.