The worst part of Fossil Pokemon is that the standard support for seaching out basics doesn't work on them ... yet most decks with a Fossil Pokemon will need that same support for their other Pokemon.
So *in addition* to Call, Roseanne's, Bebe's, and such the deck will need either a Fossil searching starter (Relcanth) or lots of Fossil Excavators. That eats up plenty of space and reduces other overall options.
That NM, TSD, and such don't work on Fossils hurts some too .. and just like the supporters above they are usually needed too.
Finally Fossils have no attacks, low HP overall, and can't retreat. So in order for a Fossil start to be anything approaching useful you have to have yet another card that lets them do something (TS-1, Call Energy, Rare Candy, etc.).
I'll grant that some of the Fossil Pokemon are pretty good. But they have some serious issues when it comes to building decks that are both consistant and adaptable.