2003 Honda Accord starting issues

I have an 03 accord 2.4L that has been running into some starting issues recently. Its been in the form of a grinding starter and sometimes a no crank. I checked my battery the first night it happened and it read 12.15V on the multimeter so I took the battery to the autoparts store and had them charge it. The battery wouldn’t charge so they gave me a new one and I installed it. The car cranked over fine and I let the car idle to operating temp as its been sitting for 2 or 3 days in 15 degree weather. The next day I went to start my car and I got the grinding of the starter again and no crank. The next 5 times I tried starting the car I got no crank at all, lights on the dash stayed illuminated. An hour later the car started no problem what so ever. Does any one know where I should begin diagnoses on this?