Tying in with my story of ending up in Paris on Bastille Day from the contest entry, the person who was hosting me (no, not the girl from the plane), decided to take me to Berthillon that night, but he inexplicably couldn't find it. Guess I'll have to go back....
It must have been a tourist :-).
If you're back in Paris, PM me. I'll be happy to show you Berthillon and a few other nightspots worthy of a Road Warrior!