How do I re-level and re-lay a brick pad with a french drain underneath?
The best thing to do is not to have it drain under the patio -- when you change the moisure content of soil, it can compact differently, or wash out, both of which could cause the problems you're seeing.  If you can, change the drain there so you're using non-perforated pipe, and run it out further to a drainage field past the bricked area.

The problem is, you want to compact the soil for the patio, which will reduce the air voids in the soil, making it less permeable and not drain as well, making the french drain less effective.

As it's bricked, if you slope it away from the house, you'll reduce the amount of water absorbed in that area, which should hopefully eliminate the need for a french drain to collect the water to take down to a drainage area.

If you want to get the best compaction of your soil, dig some if it out, then compact the soil, then add a few inches back in, compact again, then repeat until you're out of soil.  Then repeat for the base pack, check it for level and then start laying your pavers.