Try one of the big name restaurants in Paris for New Year's Eve if you're looking to bust the budget.
We ended up doing Lasserre on New Year's Eve a couple years back and Taillevent the night before (New Year's Eve Eve) While Lasserre was not inexpensive, Taillevent was 150 Euro per person more on New Year's Eve than Lasserre and more than twice the price of eating there the night before New Years Eve.
Cheers,
Jeff