Let's see...Thank you! Do you know if it is correct that it has to be through the male line until 1945? Mine is through the male line all of the way back except for my great grandmother who was born in the late 1800's.
First of all, you'll need to have all (yes, all) the consecutive marriage and birth certificates between yourself and TWO consecutive generations of French born in France.
That line needs to be a "male" line from the two generations of French born in France to at least 1946. And yes, that's an unsurmountable hurdle for the "ancestry" thing.
The consulate was correct to point to the Certificat de Nationalité Française (CNF).
That's the first "document" you'll need to request from the French administration.
But in order to request the CNF, you'll need the aforementioned consecutive marriage and birth certificates (those which are not "french from France" will need to be translated and legalized/apostilled).
And you'll probably need to request the two generations of French documents to the mairie of the town where your ancestors were born and got married. Typically you'll request that by e-mail/phone, and they'll reply by postal mail, with the documents enclosed.
With all that, you'll fill a form (that's downloadable from many consulates' websites) to request a CNF. You send that form (with all the documents enclosed) to France, and you'll get a reply in the following 12.
Most probably you'll get a reply that says that they cannot send you a CNF as your nationality was somehow "lost". Depending on the reason they give for that loss is that you will be able (or not) to then claim nationality based on your "links to France" through a déclaration de nationalité, that will probably involve another 6 months of waiting.
This is a "fast" description. If you describe a little bit more your case, especially the link to your "two consecutive generations of French born in France", we'll advise more in depth.