2008 Hyundai Accent has trouble starting on cold mornings

This is my wifes car, it has something like 50k or 60k miles on it. worked fine on cold mornings with the factory battery until we got a new one off the shelf at pep boys. we got the battery check and they replaced it twice, we also took it in and had the altornator and maybe the starter replaced. This is the second winter it has happend. it will eventually start but the first few times just the dash and lights come on with no starting or turning over, then the last time it will start up fine. Could it be the the very small battery?