If I remember correctly, the fossils are determined when Blathers examines them, so go with a full pockets of fossils and save before taking to him, have him examine them, if you didn't get the one you need, quit without saving and try again, sooner or later you'll have the one you're missing.
I would say that I'm less than half complete. I finished the fossils but still need a lot of artwork, bugs and fish. I haven't even started diving in my town yet!
My fossils are complete and so is the aquarium! (both fish and diving). Art collecting is slowely getting there but it's a fun process that I enjoy. It's just the bugs... I'm halfway there but I'm so terrible at bug catching, seriously...