I have had this same problem on my 08 classic since i have had it rocking back and forth in gear(sure that's what broke my detent spring

) tried everything i found on this forum. At the moment bike is starting first time every time my problem seemed to be with the main connector under the tank.Everything looked fine on inspection when pulling the connector apart but give it clean with wd40 anyway checked for lose wires shorts etc all good reconnected fired up no probs and did many times after that over next couple of hours.Went out that day stopped couple of times restarted great. Next morning went to start bike click lifted tank noticed bulge in tank was sitting on top of connector and pushing it down moved connector to the side cable tide it to frame has not been prob since.Could not find any loose or broken wires so mystery

just glad it's working

.Not sure if same problem for u but have a look at that connector and wiring in and out. Hope you get it sorted starter relay mod is well worth doing also made big difference to mine until finding connector

Also GPS sensor sorted one captains problem i believe and worked well for a while for me when i removed and cleaned it solenoid should not be a prob as you have new starter good luck my friend i feel your pain